Quicksort is a classic, efficient and divide-and-conquer sorting algorithm. It’s explained in most algorithms textbooks. But very few programmers could finish a bug-free implementation by hand. If you don’t believe it, close your browser and a try now :).

In this post, I will explain how quicksort works and explore the differences between implementations of imperative and functional programming styles.

A little history

Tony Hoare invented Quicksort in 1959 and published it in 1961. When Tony Hoare first developed Quicksort, he thought it was too simple to publish, only wrote his classic “Quicksort” paper after he was able to analyze its expected runtime.

By the way, Algol60 is the first compiler to support recursion, which helps Tony Hoare to publish the first version of code.

Tony Hoare tells the story of how he came up with the idea for the Quicksort computer sorting algorithm whilst in 1960 Moscow.

How Quicksort works

The basic steps for Quicksort are:

• If only one or no element is there, finish the sorting.

• Otherwise, we select an element as pivot, e.g. the last element.

• Compare elements with the pivot, move the smaller elements to the left side andlarger ones to the right side, then fix the pivot into proper position

• Do the same operations in the left sub-array and right sub-array.

  Quicksort is a recursive algorithm. The complexity is $O(Nlog_2N)$ on average, and the worst case is $O(N^2)$.

  To avoid the worst-case in practice, we choose the pivot randomly.

Imperative and functional programming style

Learn the different styles of implementations could be helpful for learning data structures and algorithms.

Most textbooks describe quicksort in an imperative programming style. Below code is a Ruby version:

def partition(arr, low, high)
  pos = rand(low..high) # random choose pivot
  arr[pos], arr[high] = arr[high], arr[pos]

  sep = low # index from the low position
  (low..high - 1).each do |j|
    if arr[j] <= arr[high]
      arr[sep], arr[j] = arr[j], arr[sep]
      sep += 1
    end
  end
  arr[sep], arr[high] = arr[high], arr[sep]
  sep
end

def quick_sort(arr, low, high)
  if low < high
    pi = partition(arr, low, high)
    quick_sort(arr, low, pi - 1)
    quick_sort(arr, pi + 1, high)
  end
end

As quicksort is a recursive algorithm, it’s natural to implement it in a functional programming style. I was shocked when I first saw this one line quicksort in Ruby:

def qsort(a)
  (x=a.pop) ? qsort(a.select { |i| i <= x }) + [x] + qsort(a.select { |i| i > x }) : []
end

a.select filters the elements smaller or bigger than the pivot, then we construct a new array with left-subarray + [pivot] + right-subarray. If you know a programming language with pattern match, it will be more simple. Below is a Haskell implementation:

qsort n = case n of
 []->[]
 (x:xs)-> qsort[a|a<-xs, a<=x] ++ [x] ++ qsort[a|a<-xs, a>x]

The differences

Imperative programming is the dominant programming paradigm currently.

Most of the mainstream programming languages designed to primarily support imperative programming, such as C, Java, Python, etc.

Variables are used to track the current “state” of a program in imperative programming. So many parts of the code are assigning values to variables, which will introduce side effect.

Someone may argue the above imperative version will perform better. As it does not need to allocate memory constantly.

Actually, many modern programming languages implemented with optimization in the compiler(or interpreter) for functional programming.

Let’s do a benchmark for the above two versions. We generate 100000 random numbers as input:

A little surprise, the functional version performs better than the imperative version.

Other optimizations

See the result of the benchmark, how quick is Ruby’s builtin sort!

Ruby’s Qsort is almost 150 lines of C code and similar to GNU’s version.

There are some other variants for optimization, Kushagra-Ortiz-Qiao-Munro is a Three-pivot variant of quicksort.

Algorithms, Robert Sedgewick and Kevin Wayne describes well with some wonderful illustrations.

TypeOcaml showed the “Immutable” of functional programming with quicksort as an example.