17 Chapter 17 Solutions

Solution to Challenge 1

You’re starting with the following list:

var list = [46, 500, 459, 1345, 13, 999];

LSD-Radix Sort

Modify your radixSort extension by adding the following print statement at the bottom of the while loop:

print(buckets);

Then when you call list.radixSort(), you’ll see the following output:

[[500], [], [], [13], [], [1345], [46], [], [], [459, 999]]
[[500], [13], [], [], [1345, 46], [459], [], [], [], [999]]
[[13, 46], [], [], [1345], [459], [500], [], [], [], [999]]
[[13, 46, 459, 500, 999], [1345], [], [], [], [], [], [], [], []]

This shows the values in the buckets at the end of all four rounds.

MSD-Radix Sort

To see the items in your buckets on each recursion, add the following line to _msdRadixSorted right above where you set bucketOrder:

print(buckets);
// final bucketOrder = ...

Now when you call list.lexicographicalSort(), you should see the following output:

[[], [1345, 13], [], [], [46, 459], [500], [], [], [], [999]]
[[], [], [], [1345, 13], [], [], [], [], [], []]
[[], [], [], [], [1345], [], [], [], [], []]
[[], [], [], [], [], [459], [46], [], [], []]

The 13 is missing from the third set of buckets since it’s in the priority bucket.

Solution to Challenge 2

You can find the number of unique UTF-16 code units in a list of words by adding each code unit to a set:

int uniqueCharacters(List<String> words) {
  final uniqueChars = <int>{};
  for (final word in words) {
    for (final codeUnit in word.codeUnits) {
      uniqueChars.add(codeUnit);
    }
  }
  return uniqueChars.length;
}

Here’s the example list:

final words = ['done', 'ad', 'eel', 'zoo', 'adept', 'do'];
print(uniqueCharacters(words)); // 9

In this case, there are nine different letters used to write the words in the list. If you were implementing a bucket sort, you would need nine buckets.

Solution to Challenge 3

Rather than just checking if you’ve reached the most significant digit of the largest number, you can count how many numbers are left to sort. If there’s only one, then you’re finished.

extension RadixSort on List<int> {
  void radixSort() {
    const base = 10;
    var place = 1;
    // 1
    var unsorted = length;
    // 2
    while (unsorted > 1) {
      // 3
      unsorted = 0;
      final buckets = List.generate(base, (_) => <int>[]);
      forEach((number) {
        final remainingPart = number ~/ place;
        final digit = remainingPart % base;
        buckets[digit].add(number);
        // 4
        if (remainingPart ~/ base > 0) {
          unsorted++;
        }
      });
      place *= base;
      clear();
      addAll(buckets.expand((element) => element));
    }
  }
}

The numbered comments show the parts that have changed:

1. Initialize the unsorted count with however many numbers are in the list.
2. Proceed with another round of sorting as long as there is more than one number left to sort.
3. Start the counting over at the beginning of each round.
4. If the current number has more significant digits left, then increment the unsorted count.

In this way, the algorithm will stop as soon as it’s sorted all of the digits in all of the numbers except the remaining ones of the last big number. They don’t need to be sorted since this number will always be last.