20.
Quicksort
Written by Jonathan Sande
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
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 value. The pivot divides the list into three partitions: values less than the pivot, values equal to the pivot, and values greater than the pivot. In the example below, the pivot is 8, while the partition on the left has values less than 8 and the partition on the right has values greater than 8:
Quicksort continues to recursively divide each partition until there’s only a single element in each one. At this point, the list is sorted.
The quicksort algorithm isn’t stable. That is, two elements of the same value may have different final locations depending on their initial positions. For example, if you’re only sorting by numerical value, a nine of clubs might come before a nine of hearts one time, but after it another time.
In this chapter, you’ll implement quicksort and look at various partitioning strategies to get the most out of this sorting algorithm.
Example
Before implementing quicksort, here’s a step-by-step example of how the quicksort algorithm works.
Start with the following unsorted list:
The first step is to choose a pivot value. It can be any value from the list. In this case, just take the first value, which is 8:
Once you have a pivot value, you can partition the elements of the list into three sublists. Put the values smaller than 8 in the left sublist and the values larger than 8 in the right sublist. The value 8 itself is in its own sublist:
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.
In the left sublist from above, choose 2 for the pivot value, and partition the sublist:
The values 0 and -1 are still in a sublist with more than one element, so they need to be partitioned, too. Choose 0 for the pivot:
Everything on the left is partitioned now, so go back to the sublist on the right. Choose 10 for the pivot value, and partition the sublist:
You need to keep going until every sublist has less than two elements, so that includes the two 9s in the left sublist above. Partition them:
And the list is now sorted:
In the next sections, you’ll look at a few different ways to implement quicksort, but they’ll generally follow the pattern you observed above.
Naïve Implementation
Open up the starter project. In the project root, create a lib folder. Then create a new file there named quicksort.dart. Finally, add the following code to the file:
List<E> quicksortNaive<E extends Comparable<E>>(
List<E> list,
) {
// 1
if (list.length < 2) return list;
// 2
final pivot = list[0];
// 3
final less = list.where(
(value) => value.compareTo(pivot) < 0,
);
final equal = list.where(
(value) => value.compareTo(pivot) == 0,
);
final greater = list.where(
(value) => value.compareTo(pivot) > 0,
);
// 4
return [
...quicksortNaive(less.toList()),
...equal,
...quicksortNaive(greater.toList()),
];
}
import 'package:starter/quicksort.dart';
void main() {
final list = <num>[8, 2, 10, 0, 9, 18, 9, -1, 5];
final sorted = quicksortNaive(list);
print(sorted);
}
[-1, 0, 2, 5, 8, 9, 9, 10, 18]
Partitioning Strategies
In this section, you’ll look at partitioning strategies to make this quicksort implementation more efficient.
extension Swappable<E> on List<E> {
void swap(int indexA, int indexB) {
if (indexA == indexB) return;
final temp = this[indexA];
this[indexA] = this[indexB];
this[indexB] = temp;
}
}
Lomuto’s Algorithm
Lomuto’s partitioning algorithm always chooses the last element as the pivot value. The algorithm then partially sorts the list by putting lower values before the pivot and higher ones after it. Finally, Lomuto returns the index of the pivot location within the list.
Example
In the following list, the pivot value is 5 since this is the last value in the list. You then set a pivot index pointing to the beginning of the list. This index is where the pivot will go after the partitioning is over. You also use the index i to iterate through the list.
Implementation
Add the Lomuto partitioning function to lib/quicksort.dart:
// 1
int _partitionLomuto<E extends Comparable<E>>(
List<E> list,
int low,
int high,
) {
// 2
final pivot = list[high];
// 3
var pivotIndex = low;
for (int i = low; i < high; i++) {
if (list[i].compareTo(pivot) <= 0) {
list.swap(pivotIndex, i);
pivotIndex += 1;
}
}
// 4
list.swap(pivotIndex, high);
return pivotIndex;
}
void quicksortLomuto<E extends Comparable<E>>(
List<E> list,
int low,
int high,
) {
if (low >= high) return;
final pivotIndex = _partitionLomuto(list, low, high);
quicksortLomuto(list, low, pivotIndex - 1);
quicksortLomuto(list, pivotIndex + 1, high);
}
Testing it Out
You can try out Lomuto’s quicksort by returning to bin/start.dart and replacing the contents of main with the following code:
final list = <num>[8, 2, 10, 0, 9, 18, 9, -1, 5];
quicksortLomuto(list, 0, list.length - 1);
print(list);
[-1, 0, 2, 5, 8, 9, 9, 10, 18]
Hoare’s Partitioning
Hoare’s partitioning algorithm always chooses the first element as the pivot value. Then it uses two pointers moving toward the middle from both ends. When the pointers reach values on the wrong side of the pivot, the values are swapped to the correct side.
Example
As before, start with the following unsorted list:
Implementation
Add the Hoare partitioning function to quicksort.dart:
int _partitionHoare<E extends Comparable<E>>(
List<E> list,
int low,
int high,
) {
// 1
final pivot = list[low];
var left = low - 1;
var right = high + 1;
while (true) {
// 2
do {
left += 1;
} while (list[left].compareTo(pivot) < 0);
// 3
do {
right -= 1;
} while (list[right].compareTo(pivot) > 0);
// 4
if (left < right) {
list.swap(left, right);
} else {
return right;
}
}
}
void quicksortHoare<E extends Comparable<E>>(
List<E> list,
int low,
int high,
) {
if (low >= high) return;
final leftHigh = _partitionHoare(list, low, high);
quicksortHoare(list, low, leftHigh);
quicksortHoare(list, leftHigh + 1, high);
}
Testing it Out
Try Hoare’s quicksort out by running the following in main:
final list = <num>[8, 2, 10, 0, 9, 18, 9, -1, 5];
quicksortHoare(list, 0, list.length - 1);
print(list);
[-1, 0, 2, 5, 8, 9, 9, 10, 18]
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]
Median-of-Three Strategy
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 list and use that as a pivot. This selection strategy prevents you from picking the highest or lowest element in the list.
Implementation
Add the following function to quicksort.dart:
int _medianOfThree<E extends Comparable<E>>(
List<E> list,
int low,
int high,
) {
final center = (low + high) ~/ 2;
if (list[low].compareTo(list[center]) > 0) {
list.swap(low, center);
}
if (list[low].compareTo(list[high]) > 0) {
list.swap(low, high);
}
if (list[center].compareTo(list[high]) > 0) {
list.swap(center, high);
}
return center;
}
void quicksortMedian<E extends Comparable<E>>(
List<E> list,
int low,
int high,
) {
if (low >= high) return;
var pivotIndex = _medianOfThree(list, low, high);
list.swap(pivotIndex, high);
pivotIndex = _partitionLomuto(list, low, high);
quicksortLomuto(list, low, pivotIndex - 1);
quicksortLomuto(list, pivotIndex + 1, high);
}
Testing it Out
Try this out back in bin/starter.dart by replacing the contents of main with the following code:
final list = <num>[8, 7, 6, 5, 4, 3, 2, 1];
quicksortMedian(list, 0, list.length - 1);
print(list);
[1, 2, 3, 4, 5, 6, 7, 8]
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 partition and aren’t grouped together. With Hoare’s algorithm, the situation is even worse as duplicates can be all over the place.
Example
As before, walking through an example first will make this more clear. Start with the following unsorted list, noting all the duplicates:
Implementation
Open lib/quicksort.dart. You need to keep track of the entire range of the pivot partition instead of just a single pivot index, so add a class for that:
class Range {
const Range(this.low, this.high);
final int low;
final int high;
}
Range _partitionDutchFlag<E extends Comparable<E>>(
List<E> list,
int low,
int high,
) {
// 1
final pivot = list[high];
// 2
var smaller = low;
var equal = low;
var larger = high;
while (equal <= larger) {
// 3
if (list[equal].compareTo(pivot) < 0) {
list.swap(smaller, equal);
smaller += 1;
equal += 1;
} else if (list[equal] == pivot) {
equal += 1;
} else {
list.swap(equal, larger);
larger -= 1;
}
}
// 4
return Range(smaller, larger);
}
void quicksortDutchFlag<E extends Comparable<E>>(
List<E> list,
int low,
int high,
) {
if (low >= high) return;
final middle = _partitionDutchFlag(list, low, high);
quicksortDutchFlag(list, low, middle.low - 1);
quicksortDutchFlag(list, middle.high + 1, high);
}
Testing it Out
Try out your new quicksort by returning to bin/starter.dart and replacing the contents of main with the following:
final list = <num>[8, 2, 2, 8, 9, 5, 9, 2, 8];
quicksortDutchFlag(list, 0, list.length - 1);
print(list);
[2, 2, 2, 5, 8, 8, 8, 9, 9]
Challenges
Here are a couple of quicksort challenges to make sure you have the topic down. Try them out yourself before looking at the solutions, which you can find in the Challenge Solutions section at the end of the book.
Challenge 1: Iterative Quicksort
In this chapter, you learned how to implement quicksort recursively. Your challenge here is to implement it iteratively. Choose any partition strategy.
Challenge 2: Merge Sort or Quicksort
Explain when and why you would use merge sort over quicksort.
Key Points
- 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²) time.
- Median of three finds the pivot by taking the median of the first, middle and last elements.
- Dutch national flag partitioning handles duplicate elements more efficiently.
Where to Go From Here?
The Dart sort method on List uses a quicksort when the list size is greater than 32. The quicksort implementations you made in this chapter used a single pivot value, but the Dart version uses a dual-pivot quicksort. To explore how it works, check out the source code: