34. Quicksort

Written by Vincent Ngo

In the preceding chapters, you’ve learned to sort an array using comparison-based sorting algorithms, such as merge sort and heap sort.

Quicksort is another comparison-based sorting algorithm. Much like merge sort, it uses the same strategy of divide and conquer. One important feature of quicksort is choosing a pivot point. The pivot divides the array into three partitions:

[ elements < pivot | pivot | elements > pivot ]

In this chapter, you will implement quicksort and look at various partitioning strategies to get the most out of this sorting algorithm.

Example

Open up the starter playground. A naïve implementation of quicksort is provided in quicksortNaive.swift:

public func quicksortNaive<T: Comparable>(_ a: [T]) -> [T] {
  guard a.count > 1 else { // 1
    return a
  }
  let pivot = a[a.count / 2] // 2
  let less = a.filter { $0 < pivot } // 3
  let equal = a.filter { $0 == pivot }
  let greater = a.filter { $0 > pivot }
  return quicksortNaive(less) + equal + quicksortNaive(greater) // 4
}

The implementation above recursively filters the array into three partitions. Let’s look at how it works:

1. There must be more than one element in the array. If not, the array is considered sorted.
2. Pick the middle element of the array as your pivot.
3. Using the pivot, split the original array into three partitions. Elements less than, equal to or greater than the pivot go into different buckets.
4. Recursively sort the partitions and then combine them.

Let’s now visualize the code above. Given the unsorted array below:

[12, 0, 3, 9, 2, 18, 8, 27, 1, 5, 8, -1, 21]
                     *

Your partition strategy in this implementation is to always select the middle element as the pivot. In this case, the element is 8. Partitioning the array using this pivot results in the following partitions:

less: [0, 3, 2, 1, 5, -1]
equal: [8, 8]
greater: [12, 9, 18, 27, 21]

Notice that the three partitions aren’t completely sorted yet. Quicksort will recursively divide these partitions into even smaller ones. The recursion will only halt when all partitions have either zero or one element.

Here’s an overview of all the partitioning steps:

Each level corresponds with a recursive call to quicksort. Once recursion stops, the leafs are combined again, resulting in a fully sorted array:

[-1, 1, 2, 3, 5, 8, 8, 9, 12, 18, 21, 27]

While this naïve implementation is easy to understand, it raises some issues and questions:

• Calling filter three times on the same array is not efficient.
• Creating a new array for every partition isn’t space-efficient. Could you possibly sort in place?
• Is picking the middle element the best pivot strategy? What pivot strategy should you adopt?

Partitioning strategies

In this section, you will look at partitioning strategies and ways to make this quicksort implementation more efficient. The first partitioning algorithm you will look at is Lomuto’s algorithm.

Lomuto’s partitioning

Lomuto’s partitioning algorithm always chooses the last element as the pivot. Let’s look at how this works in code.

In your playground, create a file called quicksortLomuto.swift and add the following function declaration:

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

This function takes three arguments:

• a is the array you are partitioning.
• low and high set the range within the array you will partition. This range will get smaller and smaller with every recursion.

The function returns the index of the pivot.

Now, implement the function as follows:

let pivot = a[high] // 1

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

a.swapAt(i, high) // 6
return i // 7

Here’s what this code does:

1. Set the pivot. Lomuto always chooses the last element as the pivot.
2. The variable i indicates how many elements are less than the pivot. When you encounter an element less than the pivot, swap it with the element at index i and increase i.
3. Loop through all the elements from low to high, but not including high since it’s the pivot.
4. Check to see if the current element is less than or equal to the pivot.
5. If it is, swap it with the element at index i and increase i.
6. Once done with the loop, swap the element at i with the pivot. The pivot always sits between the less and greater partitions.
7. Return the index of the pivot.

While this algorithm loops through the array, it divides the array into four regions:

1. a[low..<i] contains all elements <= pivot.
2. a[i...j-1] contains all elements > pivot.
3. a[j...high-1] are elements you have not compared yet.
4. a[high] is the pivot element.

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

Step-by-step

Look at a few steps of the algorithm to get a clear understanding of how it works. Given the unsorted array below:

[12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]

First, the last element 8 is selected as the pivot:

  0   1  2  3  4  5   6   7   8  9  10  11    12
[ 12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
  low                                        high
  i
  j

Then, the first element, 12, is compared to the pivot. It is not smaller than the pivot, so the algorithm continues to the next element:

   0  1  2  3  4  5   6   7   8  9  10  11   12
[ 12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
  low                                        high
  i
      j

The second element 0 is smaller than the pivot, so it is swapped with the element currently at index i (12) and i is increased:

  0   1  2  3  4  5   6   7   8  9  10  11   12
[ 0, 12, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
 low                                         high
      i
         j

The third element 3 is again smaller than the pivot, so another swap occurs:

  0   1  2  3  4  5   6   7   8  9  10  11   12
[ 0, 3, 12, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
 low                                         high
         i
            j

These steps continue until all but the pivot element have been compared. The resulting array is:

  0   1  2  3  4  5   6   7   8  9  10  11   12
[ 0, 3, 2, 1, 5, 8, -1, 27, 9, 12, 21, 18, |  8  ]
 low                                         high
                         i

Finally, the pivot element is swapped with the element currently at index i:

  0   1  2  3  4  5   6   7   8  9  10  11     12
[ 0, 3, 2, 1, 5, 8, -1 | 8 | 9, 12, 21, 18, |  27  ]
 low                                          high
                         i

Lomuto’s partitioning is now complete. Notice how the pivot is between the two regions of elements less than or equal to the pivot and elements greater than the pivot.

In the naïve implementation of quicksort, you created three new arrays and filtered the unsorted array three times. Lomuto’s algorithm performs the partitioning in place. That’s much more efficient!

With your partitioning algorithm in place, you can now implement quicksort:

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

Here, you apply Lomuto’s algorithm to partition the array into two regions; then, you recursively sort these regions. The recursion ends once a region has less than two elements.

You can try out Lomuto’s quicksort by adding the following to your playground:

var list = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quicksortLomuto(&list, low: 0, high: list.count - 1)
print(list)

Hoare’s partitioning

Hoare’s partitioning algorithm always chooses the first element as the pivot. Let’s look at how this works in code.

In your playground, create a file named quicksortHoare.swift and add the following function:

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

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

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

Let’s go over these steps:

1. Select the first element as the pivot.
2. Indexes i and j define two regions. Every index before i will be less than or equal to the pivot. Every index after j will be greater than or equal to the pivot.
3. Decrease j until it reaches an element that is not greater than the pivot.
4. Increase i until it reaches an element that is not less than the pivot.
5. If i and j have not overlapped, swap the elements.
6. Return the index that separates both regions.

Note: The index returned from the partition does not necessarily have to be the index of the pivot element.

Step-by-step

Given the unsorted array below:

[  12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8   ]

First, 12 is set as the pivot. Then i and j will start running through the array, looking for elements that are not less than (in the case of i) or greater than (in the case of j) the pivot. i will stop at element 12 and j will stop at element 8:

[  12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1,  8  ]
   p
   i                                         j

These elements are then swapped:

[  8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12 ]
   i                                       j

i and j now continue moving, this time stopping at 21 and -1:

[  8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12 ]
                   i                    j

Which are then swapped:

[  8, 0, 3, 9, 2, -1, 18, 27, 1, 5, 8, 21, 12 ]
                   i                    j

Next, 18 and 8 are swapped, followed by 27 and 5.

After this swap, the array and indices are as follows:

[  8, 0, 3, 9, 2, -1, 8, 5, 1, 27, 18, 21, 12 ]
                         i      j

The next time you move i and j, they will overlap:

[  8, 0, 3, 9, 2, -1, 8, 5, 1, 27, 18, 21, 12 ]
                            j   i

Hoare’s algorithm is now complete, and index j is returned as the separation between the two regions. There are far fewer swaps here compared to Lomuto’s algorithm. Isn’t that nice?

You can now implement a quicksortHoare function:

public 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)
  }
}

Try it out by adding the following in your playground:

var list2 = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quicksortHoare(&list2, low: 0, high: list.count - 1)
print(list2)

Effects of a bad pivot choice

The most crucial part of implementing quicksort is choosing the right partitioning strategy.

You have looked at three different partitioning strategies:

1. Choosing the middle element as a pivot.
2. Lomuto, or choosing the last element as a pivot.
3. Hoare, or choosing the first element as a pivot.

What are the implications of choosing a bad pivot?

Let’s start with the following unsorted array:

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

If you use Lomuto’s algorithm, the pivot will be the last element, 1. This results in the following partitions:

less: [ ]
equal: [1]
greater: [8, 7, 6, 5, 4, 3, 2]

An ideal pivot would split the elements evenly between the less than and greater than partitions. Choosing the first or last element of an already sorted array as a pivot makes quicksort perform much like insertion sort, which results in a worst-case performance of O(n²). One way to address this problem is by using the median of three pivot selection strategy. Here, you find the median of the first, middle and last element in the array and use that as a pivot. This selection strategy prevents you from picking the highest or lowest element in the array.

Let’s look at an implementation. Create a new file named quicksortMedian.swift and add the following function:

public func medianOfThree<T: Comparable>(_ a: inout [T],
                                         low: Int, high: Int) -> Int {
  let center = (low + high) / 2
  if a[low] > a[center] {
    a.swapAt(low, center)
  }
  if a[low] > a[high] {
    a.swapAt(low, high)
  }
  if a[center] > a[high] {
    a.swapAt(center, high)
  }
  return center
}

Here, you find the median of a[low], a[center] and a[high] by sorting them. The median will end up at index center, which is what the function returns.

Next, let’s implement a variant of Quicksort using this median of three:

public func quickSortMedian<T: Comparable>(_ a: inout [T],
                                           low: Int, high: Int) {
  if low < high {
    let pivotIndex = medianOfThree(&a, low: low, high: high)
    a.swapAt(pivotIndex, high)
    let pivot = partitionLomuto(&a, low: low, high: high)
    quicksortLomuto(&a, low: low, high: pivot - 1)
    quicksortLomuto(&a, low: pivot + 1, high: high)
  }
}

This code is simply a variation on quicksortLomuto that chooses the median of the three elements as a first step.

Try this out by adding the following in your playground:

var list3 = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quickSortMedian(&list3, low: 0, high: list3.count - 1)
print(list3)

This strategy is an improvement, but can we do better?

Dutch national flag partitioning

A problem with Lomuto’s and Hoare’s algorithms is that they don’t handle duplicates well. With Lomuto’s algorithm, duplicates end up in the less than partition and aren’t grouped together. With Hoare’s algorithm, the situation is even worse as duplicates can be all over the place.

A solution to organize duplicate elements is using Dutch national flag partitioning. This technique is named after the Dutch flag, which has three bands of colors: red, white and blue and is similar to how you create three partitions. Dutch national flag partitioning is an excellent technique to use if you have a lot of duplicate elements.

Let’s look at how it’s implemented. Create a file named quicksortDutchFlag.swift and add the following function:

public func partitionDutchFlag<T: Comparable>(_ a: inout [T],
                                              low: Int, high: Int,
                                              pivotIndex: Int)
                                              -> (Int, Int) {
  let pivot = a[pivotIndex]
  var smaller = low // 1
  var equal = low // 2
  var larger = high // 3
  while equal <= larger { // 4
    if a[equal] < pivot {
      a.swapAt(smaller, equal)
      smaller += 1
      equal += 1
    } else if a[equal] == pivot {
      equal += 1
    } else {
      a.swapAt(equal, larger)
      larger -= 1
    }
  }
  return (smaller, larger) // 5
}

You will adopt the same strategy as Lomuto’s partition by choosing the last element as the pivotIndex. Let’s go over how it works:

1. Whenever you encounter an element less than the pivot, move it to index smaller. This rule means that all elements that come before this index are less than the pivot.
2. Index equal points to the next element to compare. Elements that are equal to the pivot are skipped, which means that all elements between smaller and equal are equal to the pivot.
3. Whenever you encounter an element greater than the pivot, move it to index larger. This rule means that all elements that come after this index are greater than the pivot.
4. The main loop compares elements and swaps them if needed. This process continues until index equal moves past index larger, meaning all elements have been moved to their correct partition.
5. The algorithm returns indices smaller and larger. These point to the first and last elements of the middle partition.

Step-by-step

Let’s go over an example using the unsorted array below:

[ 12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8 ]

Since this algorithm is independent of a pivot selection strategy, adopt Lomuto and pick the last element 8.

Note: For practice, try a different strategy, such as median of three.

Next, you set up the indices smaller, equal and larger:

[12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
  s
  e
                                          l

The first element to be compared is 12. Since it is larger than the pivot, it is swapped with the element at index larger, and this index is decremented.

Note that index equal is not incremented, so the element that was swapped in (8) is compared next:

[8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12]
 s
 e
                                      l

Remember that the pivot you selected is still 8. 8 is equal to the pivot, so you increment equal:

[8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12]
 s
    e
                                      l

0 is smaller than the pivot, so you swap the elements at equal and smaller and increase both pointers:

[0, 8, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12]
    s
       e
                                      l

And so on.

Note how smaller, equal and larger partition the array:

• Elements in [low..<smaller] are smaller than the pivot.
• Elements in [smaller..<equal] are equal to the pivot.
• Elements in [larger>..high] are larger than the pivot.
• Elements in [equal...larger] haven’t been compared yet.

To understand how and when the algorithm ends, let’s continue from the second-to-last step:

[0, 3, -1, 2, 5, 8, 8, 27, 1, 18, 21, 9, 12]
                 s
                        e
                           l

Here, 27 is being compared. It is greater than the pivot, so it is swapped with 1 and index larger is decremented:

[0, 3, -1, 2, 5, 8, 8, 1, 27, 18, 21, 9, 12]
                 s
                       e
                       l

Even though equal is now equal to larger, the algorithm isn’t complete.

The element currently at equal hasn’t been compared yet. It is smaller than the pivot, so it is swapped with 8, and both indices smaller and equal are incremented:

[0, 3, -1, 2, 5, 1, 8, 8, 27, 18, 21, 9, 12]
                    s
                          e
                       l

Indices smaller and larger now point to the first and last elements of the middle partition. By returning them, the function marks the boundaries of the three partitions.

You’re now ready to implement a new version of quicksort using Dutch national flag partitioning:

public func quicksortDutchFlag<T: Comparable>(_ a: inout [T],
                                              low: Int, high: Int) {
  if low < high {
    let (middleFirst, middleLast) =
      partitionDutchFlag(&a, low: low, high: high, pivotIndex: high)
    quicksortDutchFlag(&a, low: low, high: middleFirst - 1)
    quicksortDutchFlag(&a, low: middleLast + 1, high: high)
  }
}

Notice how recursion uses the middleFirst and middleLast indices to determine the partitions that need to be sorted recursively. Because the elements equal to the pivot are grouped together, they can be excluded from the recursion.

Try out your new quicksort by adding the following in your playground:

var list4 = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quicksortDutchFlag(&list4, low: 0, high: list4.count - 1)
print(list4)

That’s it!

Key points

• The naïve partitioning creates a new array on every filter function; this is inefficient. All other strategies sort in place.
• Lomuto’s partitioning chooses the last element as the pivot.
• Hoare’s partitioning chooses the first element as its pivot.
• An ideal pivot would split the elements evenly between partitions.
• Choosing a bad pivot can cause quicksort to perform in O(n²).
• Median of three finds the pivot by taking the median of the first, middle and last element.
• Dutch national flag partitioning strategy helps to organize duplicate elements more efficiently.