18.
Quicksort
Written by Matei Suica, Kelvin Lau and Vincent Ngo
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
In the preceding chapters, you learned to sort a list 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 list into three partitions:
[ elements < pivot | pivot | elements > pivot ]
In this chapter, you’ll implement quicksort and look at various partitioning strategies to get the most out of this sorting algorithm.
Example
Open the starter project. Inside QuicksortNaive.kt, you’ll see a naive implementation of quicksort:
fun<T: Comparable<T>> List<T>.quicksortNaive(): List<T> {
if (this.size < 2) return this // 1
val pivot = this[this.size / 2] // 2
val less = this.filter { it < pivot } // 3
val equal = this.filter { it == pivot }
val greater = this.filter { it > pivot }
return less.quicksortNaive() + equal + greater.quicksortNaive() // 4
}
This implementation recursively filters the list into three partitions. Here’s how it works:
- There must be more than one element in the list. If not, the list is considered sorted.
- Pick the middle element of the list as your pivot.
- Using the pivot, split the original list 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.
Now, it’s time to visualize the code above. Given the unsorted list 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 list 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 list:
[-1, 1, 2, 3, 5, 8, 8, 9, 12, 18, 21, 27]
While this naive implementation is easy to understand, it raises some issues and questions:
- Calling
filterthree times on the same list is not efficient? - Creating a new list 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’ll look at partitioning strategies and ways to make this quicksort implementation more efficient. The first partitioning algorithm you’ll look at is Lomuto’s algorithm.
Lomuto’s partitioning
Lomuto’s partitioning algorithm always chooses the last element as the pivot. Time to look at how this works in code.
fun<T: Comparable<T>> MutableList<T>.partitionLomuto(
low: Int,
high: Int): Int {
}
val pivot = this[high] // 1
var i = low // 2
for (j in low until high) { // 3
if (this[j] <= pivot) { // 4
this.swapAt(i, j) // 5
i += 1
}
}
this.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
Looking at a few steps of the algorithm will help you get a better understanding of how it works.
[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
fun<T: Comparable<T>> MutableList<T>.quicksortLomuto(low: Int, high: Int) {
if (low < high) {
val pivot = this.partitionLomuto( low, high)
this.quicksortLomuto( low, pivot - 1)
this.quicksortLomuto( pivot + 1, high)
}
}
"Lomuto quicksort" example {
val list = arrayListOf(12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8)
println("Original: $list")
list.quicksortLomuto(0, list.size - 1)
println("Sorted: $list")
}
Hoare’s partitioning
Hoare’s partitioning algorithm always chooses the first element as the pivot. So, how does this work in code?
fun<T: Comparable<T>> MutableList<T>.partitionHoare(low: Int, high: Int): Int {
val pivot = this[low] // 1
var i = low - 1 // 2
var j = high + 1
while (true) {
do { // 3
j -= 1
} while (this[j] > pivot)
do { // 4
i += 1
} while (this[i] < pivot)
if (i < j) { // 5
this.swapAt(i, j)
} else {
return j // 6
}
}
}
Step-by-step
Given the unsorted list 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
fun<T: Comparable<T>> MutableList<T>.quicksortHoare(low: Int, high: Int) {
if (low < high) {
val p = this.partitionHoare(low, high)
this.quicksortHoare(low, p)
this.quicksortHoare( p + 1, high)
}
}
"Hoare quicksort" example {
val list = arrayListOf(12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8)
println("Original: $list")
list.quicksortHoare( 0, list.size - 1)
println("Sorted: $list")
}
Effects of a bad pivot choice
The most important 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]
fun<T: Comparable<T>> MutableList<T>.medianOfThree(low: Int, high: Int): Int {
val center = (low + high) / 2
if (this[low] > this[center]) {
this.swapAt(low, center)
}
if (this[low] > this[high]) {
this.swapAt(low, high)
}
if (this[center] > this[high]) {
this.swapAt(center, high)
}
return center
}
fun<T: Comparable<T>> MutableList<T>.quickSortMedian(low: Int, high: Int) {
if (low < high) {
val pivotIndex = medianOfThree(low, high)
this.swapAt(pivotIndex, high)
val pivot = partitionLomuto(low, high)
this.quicksortLomuto(low, pivot - 1)
this.quicksortLomuto(pivot + 1, high)
}
}
"Median of three quicksort" example {
val list = arrayListOf(12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8)
println("Original: $list")
list.quickSortMedian( 0, list.size - 1)
println("Sorted: $list")
}
Dutch national flag partitioning
A problem with Lomuto’s and Hoare’s algorithms is that they don’t handle duplicates really 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.
fun<T: Comparable<T>> MutableList<T>.partitionDutchFlag(low: Int, high: Int, pivotIndex: Int): Pair<Int, Int> {
val pivot = this[pivotIndex]
var smaller = low // 1
var equal = low // 2
var larger = high // 3
while (equal <= larger) { // 4
if (this[equal] < pivot) {
this.swapAt(smaller, equal)
smaller += 1
equal += 1
} else if (this[equal] == pivot) {
equal += 1
} else {
this.swapAt(equal, larger)
larger -= 1
}
}
return Pair(smaller, larger) // 5
}
Step-by-step
Looking at an example using the unsorted list 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
fun<T: Comparable<T>> MutableList<T>.quicksortDutchFlag(low: Int, high: Int) {
if (low < high) {
val middle = partitionDutchFlag(low, high, high)
this.quicksortDutchFlag(low, middle.first - 1)
this.quicksortDutchFlag(middle.second + 1, high)
}
}
"Dutch flag quicksort" example {
val list = arrayListOf(12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8)
println("Original: $list")
list.quicksortDutchFlag( 0, list.size - 1)
println("Sorted: $list")
}
Challenges
Challenge 1: Using recursion
In this chapter, you learned how to implement quicksort recursively. Your challenge is to implement it iteratively. Choose any partition strategy you learned in this chapter.
Solution 1
You implemented quicksort recursively, which means you know what quicksort is all about. So, how you might do it iteratively? This solution uses Lomuto’s partition strategy.
fun<T: Comparable<T>> MutableList<T>.quicksortIterativeLomuto(low: Int, high: Int) {
val stack = Stack<Int>() // 1
stack.push(low) // 2
stack.push(high)
while (!stack.isEmpty) { // 3
// 4
val end = stack.pop() ?: continue
val start = stack.pop() ?: continue
val p = this.partitionLomuto(start, end) // 5
if ((p - 1) > start) { // 6
stack.push(start)
stack.push(p - 1)
}
if ((p + 1) < end) { // 7
stack.push(p + 1)
stack.push(end)
}
}
}
"Iterative lomuto quicksort" example {
val list = arrayListOf(12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8)
println("Original: $list")
list.quicksortIterativeLomuto( 0, list.size - 1)
println("Sorted: $list")
}
Challenge 2: Provide an explanation
Explain when and why you would use merge sort over quicksort.
Solution 2
- Merge sort is preferable over quicksort when you need stability. Merge sort is a stable sort and guarantees O(n log n). This is not the case with quicksort, which isn’t stable and can perform as bad as O(n²).
- Merge sort works better for larger data structures or data structures where elements are scattered throughout memory. Quicksort works best when elements are stored in a contiguous block.
Key points
- The naive partitioning creates a new list 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 in a more efficient way.