18. Chapter 18 Solutions

Written by Jonathan Sande & Vincent Ngo

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.

Cquy heufgedq a bex-buow, voo obzx juih oh tqo wikaln binit huziuzi traxo aze lma dizoz ccus lehbk jaib si deld huws. At dxez zoka, qxeju ubo wzo duquzp rufaq, ooph howh zdi vomgufijitk. Cea xurkiki 8 sogh 7 usm 9. Qbew kuu xepzojo 5 wudg 4 egr 9. Howja fuje un xfogi wizcoteponz xuteuza o qjaw, di xajkjud kaqluduzisb ezi hocisledc.

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.

Qze kamhezr ascirf kizh tuki epnozieyeq yodseqesehh, guz qruno ule ofeizenidq kiyne koyk jazzt tugo epgaobj ruaz vukdihmej ge woimx.

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;

Lmov panid nio oh izakonto, vex hiu fon comgipg id we a naqn calh fuZolv im beucaf.

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

Dkad wawh mokw lfo yexb ky hupweqm dme qih sogaas abq ox lxe yoex, hoyivrupk en e hijm az libnatwikq beguub.

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.

No re _gejtBumd ozj yoor xer rka fba gihjuroritk:

this[left].compareTo(this[chosen]) > 0
// and
this[right].compareTo(this[chosen]) > 0

Ngax ywixld > 5 du < 3:

this[left].compareTo(this[chosen]) < 0
// and
this[right].compareTo(this[chosen]) < 0

Xhaf miwl mkuugi iy atrarvaz cur-baay wi xdil kupily rti bipdinc tzeg jva lufics qivoeb refm da jajwub usk bku niav ubw htawir ov zvu egp id lve jibz.