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

17. Chapter 17 Solutions
Written by Kelvin Lau & Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

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);
[[500], [], [], [13], [], [1345], [46], [], [], [459, 999]]
[[500], [13], [], [], [1345, 46], [459], [], [], [], [999]]
[[13, 46], [], [], [1345], [459], [500], [], [], [], [999]]
[[13, 46, 459, 500, 999], [1345], [], [], [], [], [], [], [], []]

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 = ...
[[], [1345, 13], [], [], [46, 459], [500], [], [], [], [999]]
[[], [], [], [1345, 13], [], [], [], [], [], []]
[[], [], [], [], [1345], [], [], [], [], []]
[[], [], [], [], [], [459], [46], [], [], []]

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;
}
final words = ['done', 'ad', 'eel', 'zoo', 'adept', 'do'];
print(uniqueCharacters(words)); // 9

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