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!).