4.3. Quicksort and its Variations

• File: QuickSort.ml

One of the fastest algorithms for comparison-based sorting (i.e., sorting that only relies on the fact that two key in an arrays can be compared with each other) to date is Quicksort. Invented in 1959 by Sir Tony Hoare, this algorithm now is a part of the standard Unix library (known as qsort) and Java Developer Kit (JDK).

4.3.1. Partitioning an array

Similarly to Merge sort, Quicksort belongs to the family of divide-and-conquer algorithms: it splits the problem into multiple “simpler” sub-tasks, which are solved recursively, with a base case (array of length 0 or 1) being trivial to sort. Unlike Merge sort, the main work happens on the “divide” step, i.e., before the problem is partitioned. As Merge sort’s key ingredient is the procedure merge that creates a sorted array our of two sorted arrays of a smaller size, at the heart of Quicksort is the procedure partition, whose implementation in OCaml is shown below:

let partition arr lo hi =
  if hi <= lo then lo
  else
    let pivot = arr.(hi - 1) in
    let i = ref lo in
    for j = lo to hi - 2 do
      if arr.(j) <= pivot
      then begin
        swap arr !i j;
        i := !i + 1
      end
    done;
    swap arr !i (hi - 1);
    !i

The procedure partition takes, as arguments, and array arr and two boundaries to do the partitioning, lo and hi correspondingly. Its goal is to reposition elements in an array with respect to some “pivot” element (typically chosen randomly) and return its position i in the resulting array. All elements with positions k such that lo <= k < i will have keys that are less or equal than the one of pivot, while al elements with indices k from the range that i <= k < hi will have the keys larger than the one of pivot.

There are multiple ways to choose the pivot, typically tailored to optimise for randomness. A better choice of a pivot, which should hit closer to the “median” of the keys in the range, guarantees a better performance of the algorithm. For simplicity, we will assume the uniform distribution of keys (i.e., the probability of getting a particular key from an array at a certain position is the same), and will be always choosing as pivot the last element of the array (it could be also the first, but the algorithm would be slightly different).

The partition-ing, thus, works as follows. If the subarray is empty, it just returns its lower end. Otherwise, it picks the pivot to be its last element (arr.(hi - 1)). It then allocates two counters i and j, with j starting to iterate through the range lo ... hi. Any element with a key smaller or equal than the one pivot, gets swapped to the “beginning”, i.e., in the range lo ... i, and then i is advanced. Any element with a key larger than the one of pivot remains where it is. Therefore, at any moment all keys that are less ot equal than pivot are in the range [lo ... i) and all keys that are larger than pivot are in the range [i ... j]. Therefore, once j reaches the end (hi - 2), the only unprocessed element is pivot itself, which can be thus swapped with the element at the position i (Why is it correct? Convince yourself). The procedure returns the position of i as the position of pivot. At that moment all elements with smaller or equal keys are left of i, and all elements with larger keys are on the right of i.

4.3.2. Partitioning in action

Let us trace the execution of the partition on a small array:

# let a = [|4; 5; 1; 2; 3|];;

Now let’s instrument partition with tracing as follows:

let partition_print arr lo hi =
  let open Printf in
  if hi <= lo then lo
  else
    let pivot = arr.(hi - 1) in
    printf "pivot = %d\n" pivot;
    let i = ref lo in
    for j = lo to hi - 2 do

      printf "lo = %d to  i = %d: " lo !i;
      print_int_sub_array lo !i arr; print_newline ();
      printf "i = %d  to j = %d: " !i j;
      print_int_sub_array !i j arr; print_newline ();
      printf "j = %d  to hi = %d: " j hi;
      print_int_sub_array j (hi - 1) arr; print_newline ();
      print_newline ();

      if arr.(j) <= pivot
      then begin
        swap arr !i j;
        i := !i + 1
      end
    done;
    swap arr !i (hi - 1);
    print_int_sub_array lo hi arr; print_newline ();
    !i

Running it with a will produce the following output:

# partition_print a 0 5;;

 pivot = 3
 lo = 0 to  i = 0: [|  |]
 i = 0  to j = 0: [|  |]
 j = 0  to hi = 5: [| 4; 5; 1; 2 |]

 lo = 0 to  i = 0: [|  |]
 i = 0  to j = 1: [| 4 |]
 j = 1  to hi = 5: [| 5; 1; 2 |]

 lo = 0 to  i = 0: [|  |]
 i = 0  to j = 2: [| 4; 5 |]
 j = 2  to hi = 5: [| 1; 2 |]

 lo = 0 to  i = 1: [| 1 |]
 i = 1  to j = 3: [| 5; 4 |]
 j = 3  to hi = 5: [| 2 |]

 [| 1; 2; 3; 5; 4 |]
 - : int = 2

That is, at each loop iteration for j = 0 .. 4 (since the length is 5), we can see the three segments of the partitioned array (less-or-equal than pivot, greater than pivot and unprocessed), withe the final array being as follows with the pivot element 3 standing at the position i = 2:

# a;;
- : int array = [|1; 2; 3; 5; 4|]

4.3.3. Sorting via partitioning

Having seen the main working horse of Quicksort, namely partition, the main procedure is surprisingly simple:

let quick_sort arr =
  let rec sort arr lo hi =
    if hi - lo <= 1 then ()
    else
      let mid = partition arr lo hi in
      sort arr lo mid;
      sort arr mid hi
  in
  sort arr 0 (Array.length arr)

As a classical divide-and-conquer sorting algorithm, it does nothing for the sub-arrays of size 0 an 1. For arrays of a larger size, it performs the partitioning, obtaining the index mid of the newly acquired position of the pivot, and runs itself recursively. One might wonder: why does this work at all? The answer to that is not difficult, and follows directly from the postcondition of partition, which does all the heavy lifting. It is suggested that you answer this question by means of providing an invariant (see Exercise 6).

By the way, what do you think, why do we exclude the pivot with index mid when running sort recursively, so it is not a part of either of sub-arrays to be sorted?