## 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:

- write a
*regular* implementation in which the method simply
returns the sorted array, and - write a
*pedagogical*
implementation in which, every time we change an element of an
array, the method shows the new state of the array and waits
for the user to hit Return. (If you can also show how the tree
part changes that will be perfect -- and will bring you extra
credit.)

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.