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

18. Chapter 18 Solutions
Written by Jonathan Sande & Vincent Ngo

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

Heapsort requires two steps:

  1. Converting a list to a heap.
  2. Repeatedly moving the root of the heap to an ordered list.

Step one is where you’ll find the difference in the number of comparisons needed.

5, 4, 3, 2, 1

[5, 4, 3, 2, 1] will yield the fewest number of comparisons since it’s already a max-heap and no swaps take place.

5 7 2 3 3 3 9 2 9 7

1, 2, 3, 4, 5

[1, 2, 3, 4, 5] will yield the most number of comparisons. You first compare 2 with 4 and 4 with 5. Since 2 is smaller, you swap it with 5. Then you compare 1 with 5 and 5 with 3. Since 1 is smaller, you sift it down, swapping it with the 5. The down-sift now requires comparing 1 with 4 and 4 with 2, which will lead to swapping 1 with 4.

3 4 6 2 0 1 3 5 7 6 7 8 3 3 6

Solution to Challenge 2

There are multiple ways to sort in descending order.

Using reversed

The easiest solution is to simply use the reversed method on List:

final list = [6, 12, 2, 26, 8, 18, 21, 9, 5];
final ascending = heapsort(list);
final descending = ascending.reversed;

Reimplementing Heapsort

If you’re using the heapsort function that you implemented earlier in the chapter, then replace Priority.min with Priority.max.

List<E> descendingHeapsort<E extends Comparable<dynamic>>(List<E> list) {
  final heap = Heap<E>(
    elements: list.toList(),
    priority: Priority.max, // changed
  );
  final sorted = <E>[];
  while (!heap.isEmpty) {
    final value = heap.remove();
    sorted.add(value!);
  }
  return sorted;
}

Reimplementing heapsortInPlace

It’s also easy to reimplement your heapsortInPlace extension to sort in ascending order. Again, all you have to do is change the heap priority.

this[left].compareTo(this[chosen]) > 0
// and
this[right].compareTo(this[chosen]) > 0
this[left].compareTo(this[chosen]) < 0
// and
this[right].compareTo(this[chosen]) < 0
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