CSCI 203 Project #4

Sorting Tests

Purpose: This project will give you experience with the various sorting algorithms, and a feel for what “big Oh” notation means.

Description: You are to implement three functions, each of which performs a different sort. The first function should implement quicksort, the second should implement heapsort, and the third should implement bubble sort. After you have these functions written and debugged, you are to run timing tests on them. Your main program should initialize the data array to be sorted, and then read the system clock time, call the first sort, and when it returns, read the system clock time again. It should print out the sort name and the difference of the stop and start times. It should then reinitialize the data array as it was before the first sort, and call the second sort, recording the beginning and ending times, and reporting the difference again. Finally it should to the same for the third sort.

You should run your main program six times, once on each of six different data sets, and should record the output in each case. Your first dataset should consist of 100 random numbers, while the second should consist of those 100 numbers in sorted order. The third data set should consist of 10,000 random numbers, while the fourth should consist of those 10,000 random numbers in sorted order. Finally, the fifth data set should consist of 1,000,000 random numbers, and the sixth should consist of those 1,000,000 random numbers in sorted order.

Since the random number generator in VC++ is so bad, you should implement the linear congruential random number generator

nextnum = 1664525L * lastnum + 1013904223L;

and use this to generate your data files.

You should turn in your program code, including the code you used to generate your data files. You should also turn in the output of the six runs, appropriately labeled.

Turnin: You should turn in a zipped file containing your source file(s), including the code you used to generate your data files. You should also turn in the output of your six test runs, as six files, each appropriately labeled. As usual, include a README file that describes any special or unique features of your program, as well as instructions as to how to compile and run it.

Hints: This should be the easiest program yet, but don’t put it off til the last minute because it still is a fair amount of work!