Assignment 1 solutions #

Heapsort #

With the goal of non-decreasing order.

Sink each parent starting with the last, and working down.

Now to sort, swap last element, reduce heap size, and sink item down

The element at the end will be put into place.

Running time for sink is O(lg(n)) Running time for entire sort is O(nlg(n)) worst case, best case)

Space complexity for sink is O(1) Space complexity for sort is O(1)