Assignment III

Due date Feb.20.

In this assignment you will program and test the performance of Heapsort. Using the programming language of your choice, write heapsort in two versions:

a) The standard version in which the Sift procedure exchanges a parent with one of its children only if the child is larger.

b) The Dewar optimized version, in which Sift first moves the root uncondionally to its lowest point, and then moves it up to the correct place.

Instrument both versions to count the number of comparisons performed.

Write a driver program that creates arrays of numbers, using a random number generator, and invokes each version of Heapsort on it. To get meaningful results, use arrays of size 1000, 5000, 10,000 .. 100,000, and make several experiments for each size.

Finally, verify that the number of comparisons is O (n log n), and find the rough constant of proportionality.

Note that the random number generator will in general produce duplicate values from time to time. Make sure that the algorithm works properly in the presence of duplicate values (no need to make sure that there are no duplicates).

Your program should include a simple predicate Is_Sorted, that verifies that after calling heapsort the contents of the array are indeed ordered.

Please submit a listing of your program, and the output. As for any program, you should make sure that it is properly commented and easy to read (you should always write programs under the assumption that they are interesting enough that someone, some day, will want to look at it and understand how it works!).