34.
Quicksort
Written by Vincent Ngo
Heads up... You’re accessing parts of this content for free, with some sections shown as text.
Heads up... You’re accessing parts of this content for free, with some sections shown as text.
Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
Unlock now
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:
- There must be more than one element in the array. If not, the array is considered sorted.
- Pick the middle element of the array as your pivot.
- Using the pivot, split the original array into three partitions. Elements less than, equal to or greater than the pivot go into different buckets.
- 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
filterthree 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.
public func partitionLomuto<T: Comparable>(_ a: inout [T],
low: Int,
high: Int) -> Int {
}
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
[ 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]
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
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
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
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
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
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
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)
}
}
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.
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
}
}
}
Step-by-step
Given the unsorted array below:
[ 12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8 ]
[ 12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8 ]
p
i j
[ 8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12 ]
i j
[ 8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12 ]
i j
[ 8, 0, 3, 9, 2, -1, 18, 27, 1, 5, 8, 21, 12 ]
i j
[ 8, 0, 3, 9, 2, -1, 8, 5, 1, 27, 18, 21, 12 ]
i j
[ 8, 0, 3, 9, 2, -1, 8, 5, 1, 27, 18, 21, 12 ]
j i
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)
}
}
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.
[8, 7, 6, 5, 4, 3, 2, 1]
less: [ ]
equal: [1]
greater: [8, 7, 6, 5, 4, 3, 2]
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
}
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)
}
}
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)
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.
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
}
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 ]
[12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
s
e
l
[8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12]
s
e
l
[8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12]
s
e
l
[0, 8, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12]
s
e
l
[0, 3, -1, 2, 5, 8, 8, 27, 1, 18, 21, 9, 12]
s
e
l
[0, 3, -1, 2, 5, 8, 8, 1, 27, 18, 21, 9, 12]
s
e
l
[0, 3, -1, 2, 5, 1, 8, 8, 27, 18, 21, 9, 12]
s
e
l
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)
}
}
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)
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.