The quick sort algorithm is an updated version of the merge sort algorithm with faster in-memory sorting capability. It is widely used in average-case as against worst-case scenarios. It is also efficient in terms of memory utilization, as it does not require the secondary vector when performing the merge operation. Quick sort can be accessed in R using functions such as sort (base) and quick sort (rje). It is also called partition-exchange sort. Like merge sort, quick sort also requires recursive implementation for effective execution.

The following is the three-step execution methodology of the quick sort algorithm for a given input vector V with n elements:

The following R code implements the recursive form of the quick sort algorithm:

Quick_Sort <- function(V,n) { 
  if (n <= 1) return(V) 
  left <- 0 ##start from left prior first element 
  right <- n  ##start from rightmost element 
  v <- V[n] ## initialize last element as pivot element 
 
  ## Partition implementation 
  repeat { 
    while (left < n && V[left+1]  < v) left <- left+1 
    while (right > 1 && V[right-1] >= v) right <- right-1 
    if (left >= right-1) break 
    ## Swap elements 
    temp <- V[left+1] 
    V[left+1] <- V[right-1] 
    V[right-1] <- temp 
  } 
 
  ## Recursive implementation of Quick sort 
  if (left == 0) return(c(V[n], Quick_Sort(V[1:(n-1)],n=(n-1)))) 
  if (right == n) return(c(Quick_Sort(V[1:(n-1)],n=(n-1)), V[n])) 
  return( c(Quick_Sort(V[1:left],n=left), V[n],    Quick_Sort(V[(left+1):(n-1)],n=(n-left-1)))) 
}

The R code begins with initializing the left and right indices. The left index represents the position of an element prior to the first element in the vector, and the right index represents the position of the last element in the vector. Then, the last element is considered as the pivot element for the corresponding input vector. Consider the following numeric vector with 16 elements:

Figure 5.7: An example of a 16-elements numeric vector

Now, the left and right indices start moving inward under the repeat loop till the indices meet. The inner while loops checks for bounds along with the pivot element prior to updating the left and right indices. Subsequently, the elements are swapped such that all elements toward the left of the pivot are lower than the pivot element, and all the elements toward the right are higher than the pivot element. However, the elements within the left and right subvectors need not be ordered. Figure 5.8 illustrates the first swap iterations being performed under the repeat loop:

Figure 5.8: Illustration of swap iterations

Once the left index meets the right index, the repeat loop breaks, and the recursive implementation of quick sort begins. Here, the pivot element is correctly positioned, and the remaining elements within the left and right subvectors are subject to recursive sorting. Figure 5.9 illustrates the complete implementation of the quick sort algorithm:

Figure 5.9: Illustration of quick sort

Let's analyze the asymptote of the quick sort algorithm in detail based on the number of operations performed at each step. Consider an input vector V of length n. A total of n moves are required to complete the traversing of both the left and right indices, till they meet each other. The repeat loop can be executed at most n times, and the while loop can fail at most n times. Hence, the asymptote of partition based on the pivot element is θ(n).

Consider a worst-case scenario wherein one of the subvectors has no elements upon partitioning. If this scenario occurs at each partition step, then the asymptote of the algorithm becomes θ(n²). In our algorithm, the worst-case scenario is bound to happen only when the input vector possesses all the elements in the descending order. However, this situation can be minimized upon random selection of the pivot value.

Consider a best-case scenario wherein for each iteration (of the repeat loop), the pivot value partitions the vector into two equal subvectors. Such a perfect kind of pivot will result in log n levels of partitions and n levels of traversing (by the left and right indices), which corresponds to an asymptote of θ(nlog n).

Consider an average-case scenario. Here, the behavior of the partition is between the best and worst-case scenarios, and there is an equal likelihood for any type of subvector partition. The asymptote which satisfies the recurrence relation can be defined as follows:

Thus, the closed form solution for the average-case scenario is also θ(nlog n), which is similar to that of the best-case scenario.