CS 3343 Assignment 2

Do Exercise 7.2-1, 7.2-2, 7.2-3, and 7-2.4 on page 144.
Do Exercise 7.3-1 and 7.3-2 on page 147.
Do Exercise 7.4-2 on page 149.

and

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 run on one of the UTSA Sun computers for array sizes of 100, 1000, 10000, 100000 and 1000000, 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.

Hand in this assignment at the beginning of class, Thursday, February 5, 1998. Late assignments are not accepted.