R Language Vector Quicksort

I know the R language pretty well, but I made a commitment to myself to explore many of the language’s subtleties. One classic algorithm that reveals some of a programming language’s subtleties is the quicksort vector sorting algorithm.


R has a built-in quicksort function but in some rare cases you might want to modify the pivot value selection part of the algorithm. Here’s a custom implementation:

my_qsort = function(v) {
  n = length(v)
  if (n > 1) {
    pv = v[n %/% 2] # pivot value
    left = my_qsort(v[v < pv])
    mid = v[v == pv]
    right =  my_qsort(v[v > pv])
    return(c(left, mid, right))
  else return(v)

The custom quicksort is recursive — one of the very few times when recursion is a good idea. Notice the %/% operator which is integer division. And the construction v[v == pv] returns a vector where the values are the values in v that are equal to pv. Also, note that because R functions pass by value rather than by reference, even though the function operates on its input parameter v, the argument corresponding to v will not be changed.

This entry was posted in R Language. Bookmark the permalink.