20. Chapter 20 Solutions

Written by Jonathan Sande

Solution to Challenge 1

In this chapter, you implemented quicksort recursively. Here’s how you might do it iteratively.

This solution uses Lomuto’s partitioning strategy. You’ll leverage a stack to store pairs of high and low indices for sublist partitions.

void quicksortIterativeLomuto<E extends Comparable<E>>(
  List<E> list,
) {
  // 1
  var stack = Stack<int>();
  // 2
  stack.push(0);
  stack.push(list.length - 1);
  // 3
  while (stack.isNotEmpty) {
    // 4
    final high = stack.pop();
    final low = stack.pop();
    // 5
    final pivot = _partitionLomuto(list, low, high);
    // 6
    if (pivot - 1 > low) {
      stack.push(low);
      stack.push(pivot - 1);
    }
    // 7
    if (pivot + 1 < high) {
      stack.push(pivot + 1);
      stack.push(high);
    }
  }
}

Here’s how the solution works:

1. Create a stack that stores indices.
2. Push the starting low and high boundaries on the stack as initial values.
3. When the stack is empty, quicksort is complete.
4. Get the pair of high and low indices from the stack.
5. Perform Lomuto’s partitioning with the current indices. Recall that Lomuto picks the last element as the pivot and splits the partitions into three parts: elements that are less than the pivot, the pivot, and finally, elements that are greater than the pivot.
6. Once the partitioning is complete, add the lower bound’s low and high indices to partition the lower half later.
7. Similarly, add the upper bound’s low and high indices to partition the upper half later.

The results are the same as with the recursive version:

final list = <num>[8, 2, 10, 0, 9, 18, 9, -1, 5];
quicksortIterativeLomuto(list);
print(list);
// [-1, 0, 2, 5, 8, 9, 9, 10, 18]

Solution to Challenge 2

Merge sort is preferable over quicksort when you need stability. Merge sort is stable and guarantees O(n log n). These characteristics are not the case with quicksort, which isn’t stable and can perform as badly as O(n²).

Fojqe rect kahrs fejban hah livtow wina mvdaxragar ig fogu fdtowvanel lcoye obipelzr uqi trelluceg wrduitnuok qufohn. Diezkvugq xebmw rewg jdib igotachr uqo fkiboc ez o borqoqueon jxivb.