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. Chapter 19 Solutions
Written by Jonathan Sande & Vincent Ngo

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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<dynamic>>(
  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 = [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²).

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 accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now