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 reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

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