CS 2401 Extra Credit Assignment #10

Due Date: Wednesday, November 30 or Thursday, December 1, 2011, depending on the day of your lab.

Objective: The goal of this assignment is to practice heapsort.

Assignment: Implement heapsort:

Similarly to Assignment 6, a reasonable way to write a pedagogical implementation is to write an auxiliary method that displays all the elements of the array and waits for the user's reaction; then, every time you change an element of the array while sorting it, you call this auxiliary method.

Once you have implemented heapsort, use techniques described in Assignment 3 to record the computation time needed for heapsort; for sizes n = 100, 200, 300, and 400 run each several times (e.g., 100) with a randomly generated array and record, for each of the methods, how the average running time grows as a function of n. Explain, to the TA, how the dependence of running time on the array size compares with the estimate of the running time given in the book.