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

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

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

Stepping through the code of mergeSort one line at a time is probably the easiest way to understand what’s happening.

A few strategically placed print statements can also help:

List<E> mergeSort<E extends Comparable<dynamic>>(List<E> list) {
  if (list.length < 2) {
    print('recursion ending:  $list');
    return list;
  } else {
    print('recursion list in: $list');
  }

  final middle = list.length ~/ 2;
  final left = mergeSort(list.sublist(0, middle));
  final right = mergeSort(list.sublist(middle));

  final merged = _merge(left, right);
  print('recursion ending:  merging $left and $right -> $merged');
  return merged;
}

Here’s the output for sorting the list [[4, 2, 5, 1, 3]:

recursion list in: [4, 2, 5, 1, 3]
recursion list in: [4, 2]
recursion ending:  [4]
recursion ending:  [2]
recursion ending:  merging [4] and [2] -> [2, 4]
recursion list in: [5, 1, 3]
recursion ending:  [5]
recursion list in: [1, 3]
recursion ending:  [1]
recursion ending:  [3]
recursion ending:  merging [1] and [3] -> [1, 3]
recursion ending:  merging [5] and [1, 3] -> [1, 3, 5]
recursion ending:  merging [2, 4] and [1, 3, 5] -> [1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]

Solution to Challenge 2

The tricky part of this challenge is the limited capabilities of Iterable. Traditional implementations of merge sort rely on using the indices of a list. Since Iterable types have no notion of indices, though, you’ll make use of their iterator.

List<E> _merge<E extends Comparable<dynamic>>(
  Iterable<E> first,
  Iterable<E> second,
) {
  // 1
  var result = <E>[];

  // 2
  var firstIterator = first.iterator;
  var secondIterator = second.iterator;

  // 3
  var firstHasValue = firstIterator.moveNext();
  var secondHasValue = secondIterator.moveNext();

  // more to come
}
while (firstHasValue && secondHasValue) {
  // 1
  final firstValue = firstIterator.current;
  final secondValue = secondIterator.current;

  // 2
  if (firstValue.compareTo(secondValue) < 0) {
    result.add(firstValue);
    firstHasValue = firstIterator.moveNext();

  // 3
  } else if (firstValue.compareTo(secondValue) > 0) {
    result.add(secondValue);
    secondHasValue = secondIterator.moveNext();

  // 4
  } else {
    result.add(firstValue);
    result.add(secondValue);
    firstHasValue = firstIterator.moveNext();
    secondHasValue = secondIterator.moveNext();
  }
}

// more to come
if (firstHasValue) {
  do {
    result.add(firstIterator.current);
  } while (firstIterator.moveNext());
}

if (secondHasValue) {
  do {
    result.add(secondIterator.current);
  } while (secondIterator.moveNext());
}

return result;
final list = [7, 2, 6, 3, 9];
final sorted = mergeSort(list);
print(sorted);
[2, 3, 6, 7, 9]
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