Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

19. Chapter 19 Solutions
Written by Jonathan Sande

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 4 9 0 3 9 5 8 5 8

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.

5 2 1 0 9 4 4 0 8 6 6 4 8 8 4

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 = <num>[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<E>>(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