CS 3343 Assignment 2

1. Do Problem 3-3 on page 58.
2. Do Exercise 4.3-1 on page 75.
3. Do Exercises 6.1-1 and 6.1-2 on page 129.
4. Do Exercise 6.2-1, 6.2-3, and 6.2-6 on page 132.
5. Do Exercise 6.4-1 on page 136.

   and

6. Write a file called heapsort.c that works with the program main.c to test and time merge sort and heap sort. main.c is a program that accepts a single command line parameter: the size of the array to sort. It then generates a random array of integers and sorts them using merge sort and your version of heap sort, printing for each sort the amount of time taken and whether it failed in some way. heapsort.c should contain a function

   void heapsort (int v[], int n);
   

   that sorts the array v[0..n-1] using heap sort. Compile your file together with main.c with:

   cc -o main main.c heapsort.c
   

   or use a Makefile like:

   main:	main.o heapsort.o
   

   Do not modify main.c; your code should work with main.c as it is on the web page. Turn in a printout of your well commented heapsort.c and the output of the program on the computer of your choice for array sizes of 100000, 1000000 and 10000000, and anywhere you like in between. Make sure you use the same computer for each run. See if you can make your heap sort faster than merge sort by inlining functions like Left and other such tricks.