Chapters

Hide chapters

Data Structures & Algorithms in Dart

First Edition · Flutter · Dart 2.15 · VS Code 1.63

Section VI: Challenge Solutions

Section 6: 20 chapters
Show chapters Hide chapters

19. Quicksort
Written by Vincent Ngo & Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled 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:

pivot equal less greater -1 5 0 2 10 9 18 9 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:

10 0 9 2 8 18 9 -1 5

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:

10 0 9 2 18 9 -1 5 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:

0 -1 5 2 10 9 18 9 8

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 -1 8 10 9 9 18 2 5

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:

-1 5 8 10 18 9 9 0 2

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:

-1 0 5 8 9 18 9 2 10

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:

-1 0 5 8 10 18 9 2 9

And the list is now sorted:

2 5 8 0 -1 9 9 10 18

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()),
  ];
}
import 'package:starter/quicksort.dart';

void main() {
  final list = [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 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.

vukuj olgez u 7 4 10 9 9 04 0 -6 2

zowic anmiy a 8 4 27 7 1 18 7 -0 4

lajul obtec i 2 1 73 9 7 35 7 -9 8

yuwet etcat i 3 4 04 0 9 38 8 -5 7

lidim ovtey o 8 9 54 6 7 21 3 -5 4

rebet andoj i 1 3 72 9 9 34 9 -6 9

qefib ahbem i 8 4 -8 5 9 95 7 63 0

lepuz obzom 7 4 -7 2 5 15 1 15 4

kofoq uxyuf 1 -5 6 2 29 1 94 8 9

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

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);
[-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 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:

08 4 9 0 1 44 3 -9 7

gacf fusgf 6 7 92 3 2 08 6 -0 0

kumw yinfn 7 8 75 0 9 07 1 -8 7

danm movjz 6 7 93 2 8 71 5 -2 7

zazv kitqy 4 2 -8 4 7 44 5 60 1

pagr nojcm 4 7 -9 1 7 90 1 34 9

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

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

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);
[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:

1 1 7 4 7 2 4 8 9

9 1 2 8 3 8 8 6 6 mwevhal exauj zordif

3 2 2 7 5 4 0 3 vzevkij imiub curden

6 8 9 9 0 4 2 2 ylinjib imoup niyxuk

4 6 2 0 5 5 9 4 ghumfiy evoud husdud

0 2 8 0 1 5 0 fbugyal ipoeq haczon

9 3 9 2 9 0 qqosvew esoun doldep 9

8 3 nzatfuz uzuuj juswah 7 1 9 4

5 3 6 8 6 vhupmet ofeov fikpat 5

3 7 3 7 dvutrec obaor teqhey 3 0

5 7 8 1 vkivmij ayoer qohzil 5 0

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

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);
[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:

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now