19 Quicksort

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:

pivotequallessgreater-15021091898

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:

100928189-15

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:

10092189-158

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 largerthan 8 in the right sublist. The value 8 itself is in its own sublist:

0-1521091898

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:

0-1810991825

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:

-15810189902

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:

-10589189210

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:

-10581018929

And the list is now sorted:

2580-1991018

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<dynamic>>(
  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()),
  ];
}

The implementation above recursively filters the list into three sublists:

1. There must be more than one element in the list. If not, you can consider the list sorted.
2. Pick the first element in the list as your pivot value.
3. Using the pivot, split the original list into three partitions. Elements less than, equal to, or greater than the pivot go into different sublists.
4. Recursively sort the partitions and then combine them.

To try it out, open bin/starter.dart and replace the contents of the file with the code below:

import 'package:starter/quicksort.dart';

void main() {
  final list = [8, 2, 10, 0, 9, 18, 9, -1, 5];
  final sorted = quicksortNaive(list);
  print(sorted);
}

Run that and you should see the following sorted list printed in the console:

[-1, 0, 2, 5, 8, 9, 9, 10, 18]

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

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

Partitioning Strategies

In this section, you’ll look at partitioning strategies to make this quicksort implementation more efficient.

All of these strategies will sort in place by swapping values, so you’ll need a swap helper method. Add the following extension to lib/quicksort.dart:

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;
  }
}

This will allow you to use list.swap to exchange the values at two different indices.

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 values 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.

pivotindexi901028189-15

Keep increasing i until it reaches a value less than or equal to the pivot value 5. That would be 2:

pivotindexi901028189-15

Then swap the values at i and the pivot index, that is, 2 and 8:

pivotindexi901082189-15

Move the pivot index up by one. Then keep iterating i until you get to another value less than or equal to 5. That happens at 0:

pivotindexi901082189-15

Swap the 8 and 0:

pivotindexi981002189-15

Advance the pivot index by one, and advance i until the next value less than or equal to 5. That would be -1:

pivotindexi981002189-15

Swap 10 and -1:

pivotindexi98-102189105

i is finished with its work. Advance the pivot index:

pivotindex98-102189105

The last step is to swap the pivot with the value at the pivot index:

pivotindex9-1021891058

The list is now partitioned. Smaller values are to the left of 5 and larger values are to the right.

Implementation

Add the Lomuto partitioning function to lib/quicksort.dart:

// 1
int _partitionLomuto<T extends Comparable<dynamic>>(
  List<T> 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;
}

Here are the highlights:

1. low and high are the index values of the range that you want to partition within the list. This range will get smaller and smaller with every recursion.
2. Lomuto always chooses the last element as the pivot.
3. pivotIndex will keep track of where the pivot value needs to go later. As you loop through the elements, you swap any value less than or equal to the pivot with the value at the pivotIndex. Then advance pivotIndex.
4. Once done with the loop, swap the value at pivotIndex with the pivot. The pivot always sits between the less and greater partitions.

That function only partitioned a single sublist. You still need to use recursion to implement the final sort. Add the following function to quicksort.dart:

void quicksortLomuto<E extends Comparable<dynamic>>(
  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);
}

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

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 = [8, 2, 10, 0, 9, 18, 9, -1, 5];
quicksortLomuto(list, 0, list.length - 1);
print(list);

Run this to see the same result as before:

[-1, 0, 2, 5, 8, 9, 9, 10, 18]

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

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 that are on the wrong side of the pivot, the values are swapped to the correct side.

Example

As before, start with the following unsorted list:

100928189-15

Since Hoare’s algorithm chooses the first element, 8 is the pivot value. The left pointer also starts here. The right pointer starts at the right:

leftright901028189-15

5 is less than the pivot 8, so it should be on the left. Swap 5 and 8:

leftright901025189-18

You can move the left pointer to the right until it gets to a value larger than 8. That would be 10. Likewise, move the right pointer to the left until it gets to a value smaller than 8. That would be -1:

leftright901025189-18

Swap 10 and -1 to put them in their correct partitions:

leftright90-125189108

Keep moving the pointers inward. The left pointer will move until it hits 9, and the right pointer will move until it hits 0.

leftright90-125189108

The pointers have crossed each other now, so the partitioning is finished. Note that the pivot value 8 isn’t in the middle. That means Hoare partitioning really only creates two partitions rather than three.

There are far fewer swaps with Hoare’s algorithm compared to Lomuto’s algorithm. Isn’t that nice?

Implementation

Add the Hoare partitioning function to quicksort.dart:

int _partitionHoare<T extends Comparable<dynamic>>(
  List<T> 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;
    }
  }
}

Here are the steps:

1. Select the first element as the pivot value.
2. Keep increasing the left index until it comes to a value greater than or equal to the pivot.
3. Keep decreasing the right index until it reaches a value that’s less than or equal to the pivot.
4. Swap the values at left and right if they haven’t crossed yet. Otherwise, return right as the new dividing index between the two partitions. It will be the high end of the left sublist on the next recursion.

You can now implement the quicksortHoare function. Add the following code to quicksort.dart:

void quicksortHoare<E extends Comparable<dynamic>>(
  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);
}

The value passed back from _partitionHoare is the high value of the left partition. So to get the low value of the right partition just add one. You keep recursively passing these range indices back into quicksortHoare until the partitions all have a length of zero or one. At that point, the list is sorted.

Testing it Out

Try Hoare’s quicksort out by running the following in main:

final list = [8, 2, 10, 0, 9, 18, 9, -1, 5];
quicksortHoare(list, 0, list.length - 1);
print(list);

As before, you should see the sorted results:

[-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.

You’ve looked at two different partitioning strategies so far:

1. Choosing the last element as a pivot.
2. Choosing the first element as a pivot.

What are the implications of choosing a bad pivot?

Take the following list as an example:

[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 and greater partitions. Choosing the first or last element of an already sorted list as a pivot makes quicksort perform much like insertion sort, which results in a worst-case performance of O(n²).

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<T extends Comparable<dynamic>>(
  List<T> 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;
}

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

Next, implement a variant of quicksort using this median of three:

void quicksortMedian<E extends Comparable<dynamic>>(
  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);
}

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

Testing it Out

Try this out back in bin/starter.dart by replacing the contents of main with the following code:

final list = [8, 7, 6, 5, 4, 3, 2, 1];
quicksortMedian(list, 0, list.length - 1);
print(list);

Run that and you’ll see the following sorted list:

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

This strategy is an improvement, but there are still issues in some situations.

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.

A solution to handle duplicate elements is Dutch national flag partitioning. This technique is named after the Dutch flag, which has three horizontal colored bands of red, white and blue. These three bands are analogous to the three partitions used in the sorting algorithm: values less than the pivot, equal to the pivot, and greater than the pivot. The key here is that when you have multiple values equal to the pivot, they all go in the middle partition. Dutch national flag partitioning is an excellent technique to use if you have a lot of duplicate elements.

Example

As before, walking through an example first will make this more clear. Start with the following unsorted list, noting all the duplicates:

929285828

You’ll use three pointers named smaller, equal and larger. The smaller and equal pointers start at the low end, and the larger pointer starts at the high end:

929285828smallerequallarger

You could choose anything for the pivot, but for this example, choose the last value. That would be 8. Then compare the value at equal to the pivot. They’re the same, so move equal up. You now have one value in the “pivot” partition:

92925828smallerequallarger

The value at equal is 2 now, which is smaller than the pivot 8, so swap the values at equal and smaller. Then advance both pointers. You now have one value in the “smaller” partition as well:

92925828smallerequallarger

The value at equal is again 2. Since this is smaller than 8, swap equal and smaller. Then advance both pointers:

99225828smallerequallarger

Now the value at equal is 8. That’s the same as the pivot, so advance the equal pointer:

9922528smallerequallarger

The value at equal is 9, which is larger than 8, so swap the values at equal and larger. Then move the larger pointer down. There’s now a value in the “larger” partition:

892252smallerequallarger9

The equal pointer is pointing at another 8 so advance equal. There are three values in the middle partition now, that is, the pivot partition:

22smallerequallarger9529

equal is pointing at 5, which is smaller than 8, so swap the values at smaller and equal. Then advance both of these pointers:

92252smallerequallarger9

Now equal is pointing at 9. This is larger than the pivot 8, so swap the values at equal and larger. Then move larger down:

2225smallerequallarger99

There’s one more step. equal is pointing at 2. Since this is smaller than 8, swap the values at smaller and equal. Then advance both pointers:

2252smallerequallarger99

Now equal has passed larger. This means the partitioning is finished.

The ranges before smaller and after larger will be recursively partitioned using the same algorithm. However, the range from smaller to larger is the pivot partition and it’s finished. It doesn’t need to be further partitioned.

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;
}

The parameters low and high are both inclusive. Range uses these names instead of start and end to avoid confusion since many APIs define endas an exclusive index.

Now add the partitioning function to quicksort.dart as well:

Range _partitionDutchFlag<T extends Comparable<dynamic>>(
  List<T> 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);
}

The code above is a direct implementation of the algorithm you observed in the step-by-step description:

1. Choose the last value as the pivot. This choice is somewhat arbitrary. You could also use the median-of-three strategy.
2. Initialize smaller and equal at the beginning of the list and larger at the end of the list.
3. Compare the value at equal with the pivot value. Swap it into the correct partition if needed and advance the appropriate pointers.
4. The algorithm returns indices smaller and larger. These point to the first and last elements of the middle partition.

You’re now ready to implement a new version of quicksort using Dutch national flag partitioning. Add the following method to quicksort.dart:

void quicksortDutchFlag<E extends Comparable<dynamic>>(
  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);
}

Notice how the function uses the middle.low and middle.high 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.

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 = [8, 2, 2, 8, 9, 5, 9, 2, 8];
quicksortDutchFlag(list, 0, list.length - 1);
print(list);

Run that and you should see the sorted list below:

[2, 2, 2, 5, 8, 8, 8, 9, 9]

Nice, an efficient way to sort lists with lots of duplicates!

If any of the descriptions or code samples in this chapter were confusing, consider using the debugger in your IDE to step through each line one at a time. Explanations can be misleading, but code doesn’t lie.

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:

• https://github.com/dart-lang/sdk/blob/2.15.0/sdk/lib/internal/sort.dart