CSC 17 Lab 5


NOTE: additional problems may be added later ...

Part 1:


One can use the basic characteristics of a heap to implement a sorting
    algorithm as follows:

 1. Given an array A of doubles, insert the elements one by one into
    the heap array.  Don't confuse A, the array with the doubles to
    be sorted, and the array that implements the heap.  Each insert
    takes lg(n) time and there are n elements, so this operation is
    n*lg(n).

 2. Now, reconstruct the A array (backwards) by deleting the maximum
    element from the heap one by one.  This will again take n(log n)
    time.


A. Implement this algorithm, using the code for "dheap" found on the
   homepage.  You can implement it as a function
   inside the intheap class as

	static void heapsort(double[] A)

   Call the function with a randomly generated array.  Here's how to 
   create a random array:

	double[] A = new double[n];
	for (int i=0;i<n;i++)  
	    { A[i] = Math.random()*n*5; }

B. On the class homepage you'll find a program "quickdouble.java" that 
   measures the real-time performance of the quicksort routine on doubles.
   (it's pretty darn fast!)  Using that program as a template, compare
   your algorithm against quicksort for arrays of 1, 2, 3, 4 and 5 million
   integers.  Note that the quicksort program takes a command-line argument
   indicating the number of integers to be sorted.

   Do the empirical results confirm your theory as to the behavior of
   the algorithms?  Don't just look at the raw numbers, look at the
   GROWTH RATE.  Does one consistently outperforms the other? Why?

C. You will notice that both quicksort and your heapsort algorithm
   use a randomly generated array.  Now modify both sorting programs
   so that it sorts the following array:

	double A = new double[n];
	for (int i=0;i<n;i++)  
	    { A[i] = n-i; }

   That is, the array starts out in the opposite order from being sorted.
   Run both heapsort and quicksort with this new array.  What do you
   find?  (if one of the programs crash, use arrays of smaller sizes).


D. You just implemented the heapsort algorithm by using an extra array 
   and copying values back and forth.  Can you devise an algorithm that
   uses only one array?  Hint: when deleting the root element, instead
   of throwing it away, swap it with the last element in the heap.  A similar
   optimization is required for insert.  With this optomization, the 
   array used to store the integers and the heap-implementation array 
   are one and the same (can you figure out how to change the implementation
   minimally using pointer assignments?).  For this optomization you can
   assume that the array to be sorted starts at index 1 (index 0 won't be
   used).

   Do you expect to see any timing improvements?  Reperform the timing 
   measurements.