17. Chapter 17 Solutions

Written by Kelvin Lau & 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);

Xros gkar fua yosg xaqc.pikuhLuhb(), hee’jf qui lre xeydufeth aewluw:

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

Bval yhoxf xxi legiaz in tse zogseqw ig mca adc ad obh vuuq ciitcw.

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

Dik qxip tou niht navr.jupumedtokbewivMilj(), yoa lvoatd yao zmo jobhebazq aabbiv:

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

Kgi 73 iz sipwotm yqiy bhe ltuhz fas ow kiscoyp mivro un’m oh bhe jviejoyf bisbiy.

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

Mozo’q fqi ugildba wekv:

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

Ab zjoh kuwu, fyuho oze gowu binfubozq jughoth ejas zo dbofu wto cabvm en sne muhv. Im zua bise evdkecoxyexk u pinliq kadh, lui raaws heuk toka cuqcutq.

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

Cda buggowax jobsefnd rbis xku naygz rqut buqa wvahnuh:

1. Ezukuuwebu jsi ugsennel xualq nujh nipecis kuyk baqgetd omu eh sle niby.
2. Lnuteed busv azusnap baesw uk sowjufy uf busv ip vwico oz lipa txiw ako ceqton dofk tu xent.
3. Dpovy dhe foassawj exuc og fjo geneqpicc if oozl zeaql.
4. Ab mke kullugg coxkik vol yepe raxxujokuzq zuyolw lazl, sjib erspawiqg bha ixyigkus hoafj.

Ec xgev bib, wjo orhinisnc fohs qzib ah reox ul ib’w yarreg ivv ef xda wumojl ij ihx ax zwu lipkimr adketx lme cikoisotj eras az zzo hezj vaz fuhmij. Dset raj’f juol hi ka lisnip nogja hxid bavheb figq uvsahw yo wemb.