CS 2401 Assignment #9

Due Date:
  1. for Part 1, Monday, July 30, 2012;
  2. for Part 2, Thursday, August 2, 2012.

Objective: The goal of this assignment is to practice binary search trees and heapsort.

Assignment: Implement the following sorting methods:

  1. Part 1: place elements one by one into a balanced binary search tree, and then produce the elements in the increasing order (in-order);
  2. Part 2: perform heapsort.

For each of these two methods, use techniques described in Assignment 3 to record the computation time needed for each sorting method; 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 estimates of the running time given in the book.