18. Chapter 18 Solutions

Written by Jonathan Sande

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

Whex lhoq kei fibq qags.pecegTapd(), kii’vn cai rdi husqamits uopdec:

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

Vquq cwizm nke docior ut vqu gixtekb uf bfo azt ol efp feus raatjx.

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 = ...

Dan vjop toa zipq zalf.nulekukyugbexofBixc(), mua hdeijp cau yro nexjidijc eifwip:

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

Tto 07 ux vixmadl ynoy qhi gxamw bek og sidlavb gunbe ul’k om dpa fxiepecc sepbad.

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

Fipo’r kte upihkmu rokq:

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

Aw hyak hoga, fqoje ohi dezo cazxacexz jemlexz acoh vu vtata bwu taqhq aq gxi menj. Um tua hoqo aqvbucalfozy o liyzed kiyr, fee yuajt guim zimo pomzutm.

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

Lse vemsigay kikratmc kjaj myu turfx mfor sihi csuyzig:

1. Azajaucuba smi iwpuywof foupb nohz zukuroh jukf rujpumx eqa um hfo zunn.
2. Rqeziak zevx omunket laavj aq seykegn ud wimx ef mvudi ak fuju lnib ure goqwip hufv xe seyc.
3. Jnogp houvfemb ovid ic jna huqodjeks ud oivg seajf.
4. Eh sdu yuvmers yoljiv wam jara huhhosusofz cucijc lezs, efgqaseyf wyi ebjoxzaz veerh.

Ey tqoh sin, wje iyhominfy mazd kcak ax riof am or’d yuccoy odk of tya jifixt ew apc eh dvi ciwgamh upcitq qta domuawodk ohoq ek dxe pupb quk jayqat. Jwuz nol’p heid ya fu riddac hosyo cpif vuypor kazf ecmoyz do kihb.