Handed out: 4/1/03
In class we discussed two sorting algorithms: insertion sort and quicksort. For this assignment you will do an experimental comparison of those two algorithms.
Write the insertion sort and quicksort algorithms. Write a main program that reads a letter c and a number n from the user. It starts by storing n random numbers into an array. Then, if the letter c is 'i', the main program runs the insertion sort algorithm on the array. If the letter is 'q', it runs quicksort on the array.
Design the partition algorithm used by quicksort so that it takes the first, middle and last members of an array, finds the median of those three numbers, and swaps that value with the first thing, so that the median will be used as a pivot. To do this, write a function called selectPivot that moves the correct pivot to the beginning of the array. Think carefully about selectPivot, and do a hand simulation for every possible location where the correct pivot could be (at the beginning, at the end or in the middle) to ensure that it works.
After sorting the array, print out the contents of the array, so that you can see that it is sorted. Test both algorithms. Do not continue to part 2 until you are convinced that your sorting functions are working.
Now comment out the part that prints the array. Instead, make your program say how long it took to do the sort. There is a standard function called ftime that gets the current time as a number of milliseconds since the start of January 1, 1970. (That time is called the epoch, so ftime gets the number of milliseconds since the epoch.) There have been too many milliseconds since the epoch to store in a variable of type long, so the number is stored in a structure called timeb holding two variables: time (the number of seconds) and millitm (the number of milliseconds after the last second, a number from 0 to 999).
Include header file <sys/timeb.h>. Create two variables, t1 and t2, as follows.
timeb t1, t2;Just before starting the sort, get the time using
ftime(&t1);Just after sorting, get the time again, using
ftime(&t2);Now report the difference between the times. You can compute the difference, in milliseconds, using timediff(t1,t2), where timediff is as follows.
long timediff(const timeb& t1, const timeb& t2)
{
long s1,s2,m1,m2;
s1 = t1.time;
m1 = t1.millitm;
s2 = t2.time;
m2 = t2.millitm;
return 1000*(s2 - s1) + (m2 - m1);
}
Your main program should only report the number of milliseconds needed to perform the sort. It no longer tries to print the sorted array.
Run your program for each algorithm using sizes 100, 300, 1000, 3000 and 10000. (Be sure that you create your array large enough for the largest test that you will run.) Run all of the tests on the same computer. You will get some variation in times. For each test, run the test three times, and record the median of the three times as the result time.
Draw a graph showing the running time of each algorithm for these sizes. You can also include some other sizes, for more points, if you like. Make the graph neat and readable. It should put the size on the horizontal (x) axis and the time, in milliseconds, on the vertical (y) axis.
Your Random class from exercise 5 can be used to create the random numbers. Create a random number generator object, get numbers from it, and put them into the array. When you are doing the timing, only time how long it takes to sort. Do not include the time required to put the random numbers into the array.
Turn in a printout of your program, a table of your data, and your graph, stapled together.