Quick sort

A classic example is Quicksort, an algorithm used to sort a vector of numbers from smallest to largest. For instance, suppose we wish to sort the vector (5,4,12,13,3,8,88). We first compare everything to the first element, 5, to form two subvectors: one consisting of the elements less than 5 and the other consisting of the elements greater than or equal to 5. That gives us subvectors (4,3) and (12,13,8,88). We then call the function on the subvectors, returning (3,4) and (8,12,13,88). We string those together with the 5, yielding (3,4,5,8,12,13,88), as desired. R’s vector-filtering capability and its c() function make implementation of Quicksort quite easy.

quick_sort<-function(x)
      {
   if(length(x)<=1) return(x)
            pivot<-x[1]
            rest<-x[-1]
            pivot_less<-quick_sort(rest[rest<pivot])
            pivot_greater<-quick_sort(rest[rest>=pivot])
            return(c(pivot_less,pivot,pivot_greater))
 }

 quick_sort(c(5,4,12,13,3,8,88))

## [1]  3  4  5  8 12 13 88

Note carefully the termination condition: if (length(x) <= 1) return(x) Without this, the function would keep calling itself repeatedly on empty vectors, executing forever.