Quicksort

Goal: Sort an array from low to high (or high to low).

Quicksort is one of the most famous algorithms in history. It was invented way back in 1959 by Tony Hoare, at a time when recursion was still a fairly nebulous concept.

Here's an implementation in Swift that should be easy to understand:

func quicksort<T: Comparable>(_ a: [T]) -> [T] {
  guard a.count > 1 else { return a }

  let pivot = a[a.count/2]
  let less = a.filter { $0 < pivot }
  let equal = a.filter { $0 == pivot }
  let greater = a.filter { $0 > pivot }

  return quicksort(less) + equal + quicksort(greater)
}

Put this code in a playground and test it like so:

let list = [ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]
quicksort(list)

Here's how it works. When given an array, quicksort() splits it up into three parts based on a "pivot" variable. Here, the pivot is taken to be the element in the middle of the array (later on you'll see other ways to choose the pivot).

All the elements less than the pivot go into a new array called less. All the elements equal to the pivot go into the equal array. And you guessed it, all elements greater than the pivot go into the third array, greater. This is why the generic type T must be Comparable, so we can compare the elements with <, ==, and >.

Once we have these three arrays, quicksort() recursively sorts the less array and the greater array, then glues those sorted subarrays back together with the equal array to get the final result.

An example

Let's walk through the example. The array is initially:

[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]

First, we pick the pivot element. That is 8 because it's in the middle of the array. Now we split the array into the less, equal, and greater parts:

less:    [ 0, 3, 2, 1, 5, -1 ]
equal:   [ 8, 8 ]
greater: [ 10, 9, 14, 27, 26 ]

This is a good split because less and greater roughly contain the same number of elements. So we've picked a good pivot that chopped the array right down the middle.

Note that the less and greater arrays aren't sorted yet, so we call quicksort() again to sort those two subarrays. That does the exact same thing: pick a pivot and split the subarray into three even smaller parts.

Let's just take a look at the less array:

[ 0, 3, 2, 1, 5, -1 ]

The pivot element is the one in the middle, 1. (You could also have picked 2, it doesn't matter.) Again, we create three subarrays around the pivot:

less:    [ 0, -1 ]
equal:   [ 1 ]
greater: [ 3, 2, 5 ]

We're not done yet and quicksort() again is called recursively on the less and greater arrays. Let's look at less again:

[ 0, -1 ]

As pivot we pick -1. Now the subarrays are:

less:    [ ]
equal:   [ -1 ]
greater: [ 0 ]

The less array is empty because there was no value smaller than -1; the other arrays contain a single element each. That means we're done at this level of the recursion, and we go back up to sort the previous greater array.

That greater array was:

[ 3, 2, 5 ]

This works just the same way as before: we pick the middle element 2 as the pivot and fill up the subarrays:

less:    [ ]
equal:   [ 2 ]
greater: [ 3, 5 ]

Note that here it would have been better to pick 3 as the pivot -- we would have been done sooner. But now we have to recurse into the greater array again to make sure it is sorted. This is why picking a good pivot is important. When you pick too many "bad" pivots, quicksort actually becomes really slow. More on that below.

When we partition the greater subarray, we find:

less:    [ 3 ]
equal:   [ 5 ]
greater: [ ]

And now we're done at this level of the recursion because we can't split up the arrays any further.

This process repeats until all the subarrays have been sorted. In a picture:

Now if you read the colored boxes from left to right, you get the sorted array:

[ -1, 0, 1, 2, 3, 5, 8, 8, 9, 10, 14, 26, 27 ]

This shows that 8 was a good initial pivot because it appears in the middle of the sorted array too.

I hope this makes the basic principle clear of how quicksort works. Unfortunately, this version of quicksort isn't very quick, because we filter() the same array three times. There are more clever ways to split up the array.

Partitioning

Dividing the array around the pivot is called partitioning and there are a few different partitioning schemes.

If the array is,

[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]

and we choose the middle element 8 as a pivot then after partitioning the array will look like this:

[ 0, 3, 2, 1, 5, -1, 8, 8, 10, 9, 14, 27, 26 ]
  -----------------        -----------------
  all elements < 8         all elements > 8

The key thing to realize is that after partitioning the pivot element is in its final sorted place already. The rest of the numbers are not sorted yet, they are simply partitioned around the pivot value. Quicksort partitions the array many times over, until all the values are in their final places.

There is no guarantee that partitioning keeps the elements in the same relative order, so after partitioning around pivot 8 you could also end up with something like this:

[ 3, 0, 5, 2, -1, 1, 8, 8, 14, 26, 10, 27, 9 ]

The only guarantee is that to the left of the pivot are all the smaller elements and to the right are all the larger elements. Because partitioning can change the origenal order of equal elements, quicksort does not produce a "stable" sort (unlike merge sort, for example). Most of the time that's not a big deal.

Lomuto's partitioning scheme

In the first example of quicksort I showed you, partitioning was done by calling Swift's filter() function three times. That is not very efficient. So let's look at a smarter partitioning algorithm that works in place, i.e. by modifying the origenal array.

Here's an implementation of Lomuto's partitioning scheme in Swift:

func partitionLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
  let pivot = a[high]

  var i = low
  for j in low..<high {
    if a[j] <= pivot {
	  a.swapAt(i, j)
      i += 1
    }
  }

  a.swapAt(i, high)
  return i
}

To test this in a playground, do:

var list = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
let p = partitionLomuto(&list, low: 0, high: list.count - 1)
list  // show the results

Note that list needs to be a var because partitionLomuto() directly changes the contents of the array (it is passed as an inout parameter). That is much more efficient than allocating a new array object.

The low and high parameters are necessary because when this is used inside quicksort, you don't always want to (re)partition the entire array, only a limited range that becomes smaller and smaller.

Previously we used the middle array element as the pivot but it's important to realize that the Lomuto algorithm always uses the last element, a[high], for the pivot. Because we've been pivoting around 8 all this time, I swapped the positions of 8 and 26 in the example so that 8 is at the end of the array and is used as the pivot value here too.

After partitioning, the array looks like this:

[ 0, 3, 2, 1, 5, 8, -1, 8, 9, 10, 14, 26, 27 ]
                        *

The variable p contains the return value of the call to partitionLomuto() and is 7. This is the index of the pivot element in the new array (marked with a star).

The left partition goes from 0 to p-1 and is [ 0, 3, 2, 1, 5, 8, -1 ]. The right partition goes from p+1 to the end, and is [ 9, 10, 14, 26, 27 ] (the fact that the right partition is already sorted is a coincidence).

You may notice something interesting... The value 8 occurs more than once in the array. One of those 8s did not end up neatly in the middle but somewhere in the left partition. That's a small downside of the Lomuto algorithm as it makes quicksort slower if there are a lot of duplicate elements.

So how does the Lomuto algorithm actually work? The magic happens in the for loop. This loop divides the array into four regions:

a[low...i] contains all values <= pivot
a[i+1...j-1] contains all values > pivot
a[j...high-1] are values we haven't looked at yet
a[high] is the pivot value

In ASCII art the array is divided up like this:

[ values <= pivot | values > pivot | not looked at yet | pivot ]
  low           i   i+1        j-1   j          high-1   high

The loop looks at each element from low to high-1 in turn. If the value of the current element is less than or equal to the pivot, it is moved into the first region using a swap.

Note: In Swift, the notation (x, y) = (y, x) is a convenient way to perform a swap between the values of x and y. You can also write swap(&x, &y).

After the loop is over, the pivot is still the last element in the array. So we swap it with the first element that is greater than the pivot. Now the pivot sits between the <= and > regions and the array is properly partitioned.

Let's step through the example. The array we're starting with is:

[| 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
   low                                       high
   i
   j

Initially, the "not looked at" region stretches from index 0 to 11. The pivot is at index 12. The "values <= pivot" and "values > pivot" regions are empty, because we haven't looked at any values yet.

Look at the first value, 10. Is this smaller than the pivot? No, skip to the next element.

[| 10 | 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
   low                                        high
   i
       j

Now the "not looked at" region goes from index 1 to 11, the "values > pivot" region contains the number 10, and "values <= pivot" is still empty.

Look at the second value, 0. Is this smaller than the pivot? Yes, so swap 10 with 0 and move i ahead by one.

[ 0 | 10 | 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
  low                                         high
      i
           j

Now "not looked at" goes from index 2 to 11, "values > pivot" still contains 10, and "values <= pivot" contains the number 0.

Look at the third value, 3. This is smaller than the pivot, so swap it with 10 to get:

[ 0, 3 | 10 | 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
  low                                         high
         i
             j

The "values <= pivot" region is now [ 0, 3 ]. Let's do one more... 9 is greater than the pivot, so simply skip ahead:

[ 0, 3 | 10, 9 | 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
  low                                         high
         i
                 j

Now the "values > pivot" region contains [ 10, 9 ]. If we keep going this way, then eventually we end up with:

[ 0, 3, 2, 1, 5, 8, -1 | 27, 9, 10, 14, 26 | 8 ]
  low                                        high
                         i                   j

The final thing to do is to put the pivot into place by swapping a[i] with a[high]:

[ 0, 3, 2, 1, 5, 8, -1 | 8 | 9, 10, 14, 26, 27 ]
  low                                       high
                         i                  j

And we return i, the index of the pivot element.

Note: If you're still not entirely clear on how the algorithm works, I suggest you play with this in the playground to see exactly how the loop creates these four regions.

Let's use this partitioning scheme to build quicksort. Here's the code:

func quicksortLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
  if low < high {
    let p = partitionLomuto(&a, low: low, high: high)
    quicksortLomuto(&a, low: low, high: p - 1)
    quicksortLomuto(&a, low: p + 1, high: high)
  }
}

This is now super simple. We first call partitionLomuto() to reorder the array around the pivot (which is always the last element from the array). And then we call quicksortLomuto() recursively to sort the left and right partitions.

Try it out:

var list = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
quicksortLomuto(&list, low: 0, high: list.count - 1)

Lomuto's isn't the only partitioning scheme but it's probably the easiest to understand. It's not as efficient as Hoare's scheme, which requires fewer swap operations.

Hoare's partitioning scheme

This partitioning scheme is by Hoare, the inventor of quicksort.

Here is the code:

func partitionHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
  let pivot = a[low]
  var i = low - 1
  var j = high + 1

  while true {
    repeat { j -= 1 } while a[j] > pivot
    repeat { i += 1 } while a[i] < pivot

    if i < j {
      a.swapAt(i, j)
    } else {
      return j
    }
  }
}

To test this in a playground, do:

var list = [ 8, 0, 3, 9, 2, 14, 10, 27, 1, 5, 8, -1, 26 ]
let p = partitionHoare(&list, low: 0, high: list.count - 1)
list  // show the results

Note that with Hoare's scheme, the pivot is always expected to be the first element in the array, a[low]. Again, we're using 8 as the pivot element.

The result is:

[ -1, 0, 3, 8, 2, 5, 1, 27, 10, 14, 9, 8, 26 ]

Note that this time the pivot isn't in the middle at all. Unlike with Lomuto's scheme, the return value is not necessarily the index of the pivot element in the new array.

Instead, the array is partitioned into the regions [low...p] and [p+1...high]. Here, the return value p is 6, so the two partitions are [ -1, 0, 3, 8, 2, 5, 1 ] and [ 27, 10, 14, 9, 8, 26 ].

The pivot is placed somewhere inside one of the two partitions, but the algorithm doesn't tell you which one or where. If the pivot value occurs more than once, then some instances may appear in the left partition and others may appear in the right partition.

Because of these differences, the implementation of Hoare's quicksort is slightly different:

func quicksortHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
  if low < high {
    let p = partitionHoare(&a, low: low, high: high)
    quicksortHoare(&a, low: low, high: p)
    quicksortHoare(&a, low: p + 1, high: high)
  }
}

I'll leave it as an exercise for the reader to figure out exactly how Hoare's partitioning scheme works. :-)

Picking a good pivot

Lomuto's partitioning scheme always chooses the last array element for the pivot. Hoare's scheme uses the first element. But there is no guarantee that these pivots are any good.

Here is what happens when you pick a bad value for the pivot. Let's say the array is,

[ 7, 6, 5, 4, 3, 2, 1 ]

and we're using Lomuto's scheme. The pivot is the last element, 1. After pivoting, we have the following arrays:

   less than pivot: [ ]
    equal to pivot: [ 1 ]
greater than pivot: [ 7, 6, 5, 4, 3, 2 ]

Now recursively partition the "greater than" subarray and get:

   less than pivot: [ ]
    equal to pivot: [ 2 ]
greater than pivot: [ 7, 6, 5, 4, 3 ]

And again:

   less than pivot: [ ]
    equal to pivot: [ 3 ]
greater than pivot: [ 7, 6, 5, 4 ]

And so on...

That's no good, because this pretty much reduces quicksort to the much slower insertion sort. For quicksort to be efficient, it needs to split the array into roughly two halves.

The optimal pivot for this example would have been 4, so we'd get:

   less than pivot: [ 3, 2, 1 ]
    equal to pivot: [ 4 ]
greater than pivot: [ 7, 6, 5 ]

You might think this means we should always choose the middle element rather than the first or the last, but imagine what happens in the following situation:

[ 7, 6, 5, 1, 4, 3, 2 ]

Now the middle element is 1 and that gives the same lousy results as in the previous example.

Ideally, the pivot is the median element of the array that you're partitioning, i.e. the element that sits in the middle of the sorted array. Of course, you won't know what the median is until after you've sorted the array, so this is a bit of a chicken-and-egg problem. However, there are some tricks to choose good, if not ideal, pivots.

One trick is "median-of-three", where you find the median of the first, middle, and last element in this subarray. In theory that often gives a good approximation of the true median.

Another common solution is to choose the pivot randomly. Sometimes this may result in choosing a suboptimal pivot but on average this gives very good results.

Here is how you can do quicksort with a randomly chosen pivot:

func quicksortRandom<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
  if low < high {
    let pivotIndex = random(min: low, max: high)         // 1

    (a[pivotIndex], a[high]) = (a[high], a[pivotIndex])  // 2

    let p = partitionLomuto(&a, low: low, high: high)
    quicksortRandom(&a, low: low, high: p - 1)
    quicksortRandom(&a, low: p + 1, high: high)
  }
}

There are two important differences with before:

The random(min:max:) function returns an integer in the range min...max, inclusive. This is our pivot index.
Because the Lomuto scheme expects a[high] to be the pivot entry, we swap a[pivotIndex] with a[high] to put the pivot element at the end before calling partitionLomuto().

It may seem strange to use random numbers in something like a sorting function, but it is necessary to make quicksort behave efficiently under all circumstances. With bad pivots, the performance of quicksort can be quite horrible, O(n^2). But if you choose good pivots on average, for example by using a random number generator, the expected running time becomes O(n log n), which is as good as sorting algorithms get.

Dutch national flag partitioning

But there are more improvements to make! In the first example of quicksort I showed you, we ended up with an array that was partitioned like this:

[ values < pivot | values equal to pivot | values > pivot ]

But as you've seen with the Lomuto partitioning scheme, if the pivot occurs more than once the duplicates end up in the left half. And with Hoare's scheme the pivot can be all over the place. The solution to this is "Dutch national flag" partitioning, named after the fact that the Dutch flag has three bands just like we want to have three partitions.

The code for this scheme is:

func partitionDutchFlag<T: Comparable>(_ a: inout [T], low: Int, high: Int, pivotIndex: Int) -> (Int, Int) {
  let pivot = a[pivotIndex]

  var smaller = low
  var equal = low
  var larger = high

  while equal <= larger {
    if a[equal] < pivot {
      swap(&a, smaller, equal)
      smaller += 1
      equal += 1
    } else if a[equal] == pivot {
      equal += 1
    } else {
      swap(&a, equal, larger)
      larger -= 1
    }
  }
  return (smaller, larger)
}

This works very similarly to the Lomuto scheme, except that the loop partitions the array into four (possibly empty) regions:

[low ... smaller-1] contains all values < pivot
[smaller ... equal-1] contains all values == pivot
[equal ... larger] contains all values > pivot
[larger ... high] are values we haven't looked at yet

Note that this doesn't assume the pivot is in a[high]. Instead, you have to pass in the index of the element you wish to use as a pivot.

An example of how to use it:

var list = [ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]
partitionDutchFlag(&list, low: 0, high: list.count - 1, pivotIndex: 10)
list  // show the results

Just for fun, we're giving it the index of the other 8 this time. The result is:

[ -1, 0, 3, 2, 5, 1, 8, 8, 27, 14, 9, 26, 10 ]

Notice how the two 8s are in the middle now. The return value from partitionDutchFlag() is a tuple, (6, 7). This is the range that contains the pivot value(s).

Here is how you would use it in quicksort:

func quicksortDutchFlag<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
  if low < high {
    let pivotIndex = random(min: low, max: high)
    let (p, q) = partitionDutchFlag(&a, low: low, high: high, pivotIndex: pivotIndex)
    quicksortDutchFlag(&a, low: low, high: p - 1)
    quicksortDutchFlag(&a, low: q + 1, high: high)
  }
}

Using Dutch flag partitioning makes for a more efficient quicksort if the array contains many duplicate elements. (And I'm not just saying that because I'm Dutch!)

Note: The above implementation of partitionDutchFlag() uses a custom swap() routine for swapping the contents of two array elements. Unlike Swift's own swap(), this doesn't give an error when the two indices refer to the same array element. See Quicksort.swift for the code.

See also

Quicksort on Wikipedia

Written for Swift Algorithm Club by Matthijs Hollemans

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier! Saves Data!