Lab Exercise 06.1

Sort Comparison

Problem Description:

The problem to be solved is a comparison of 4 different sort methods. The algorithms are mergesort, quicksort, insertion sort and bubblesort. The traditional wisdom concerning the efficiency of these algorithms is that the fastest sort on large numbers of data items is the quicksort followed by the mergesort, then the insertion sort and slowest of the four, the bubblesort. Is this really true? How great are the differences? The point of the exercise is three-fold,

to find, modify and use code from the Internet

to find the appropriate sort algorithm to use for a specific class of problem and

to produce a professional-looking, well-documented, printed paper.

There are many sites on the Web where the required algorithms and even complete codes can be found. Your task is to find/modify/write running test programs for each of the four sort methods. You should create use 4 separate testing programs since we want the tests to be completely independent. The result will be to fill-in the values in the following table. You are welcome to use your own code for the Mergesort.

Sort	100	1000	10000	100000	1000000	10000000
Quicksort
Mergesort
Insertion
Bubble

The first column will contain the time taken to sort 100 data points with each of the sort programs. The second column will concern itself with 1000 data points etc. You will generate a random sequence of numbers to initialize the unsorted array. These numbers will be of type double so you may have to modify the downloaded program code to sort data of type double (if it doesnt do so already).

Every sort will be able to manage a few thousand data points but some algorithms may be overloaded by the final column (10,000,000 values). Such overloaded behavior is unpredictable. If this occurs merely put a large X in the appropriate place in the table. Some sorts may take an inordinately long time on the larger data sets. You may place a limit of approximately 30 minutes (wristwatch time) on any single test. If the test runs past 30 minutes, indicate this in the appropriate place in the table by writing >30 min.

Your test program will also test the result for correct sorted order since a sort program that runs quickly but incorrectly is of no use. This test will be done by comparing each adjacent pair of sorted items, sequentially, through the entire array.

The code to generate a random sequence of numbers is reproduced here for your convenience.

// fill an existing array with random doubles

// The value n will be the number of values to create

for (int i = 0; i < n; ++i)

{

ArrayToBeSorted[i] = Math.random( );

}

There are several ways to measure sorting time but a simple one is shown below.

long time1 = System.nanoTime();

// here is the place where you place the code

// or the call to code to be timed.

long elapsed = System.nanoTime() - time1;

The resulting time will be in nanoseconds so divide by 1,000,000 to get milliseconds or by 1,000,000,000 to get seconds.

The code to test for correct sort results consists in comparing each adjacent pair of sorted values and flagging the first pair that doesnt occur in the correct order. A sample code is shown below for your convenience.

// test the sorted array for accuracy

// The array will be assumed to be in ascending order

for (int i = 0; i < n-1; ++i)

{

if (SortedArray[i] >= SortedArray[i+1])

{

System.out.println( Array out of order.);

break;

}

}

Exercise result:

The correct result of this exercise will be a written paper, detailing your results including the table shown above. You should explain what you expect from the test and then display the table showing the actual results. Follow that up with an explanation of what the table values mean and an attempt to explain any deviation from what you expected. A printout of all code that you used will be attached to the paper. This paper should be done in a professional manner which means a college-level minimum of grammatical and spelling errors, relatively detailed descriptions of the points which you wish to make and it should be printed on actual paper and submitted to me. This is the only exercise in this course that I want printed and I will accept it in no other manner.

Additionally: I may ask to see one or more of your tests performed while I watch. I may ask to inspect your code to prevent the possibility of faking the results. Dont laugh; this has happened in the past!