Purpose: Now that we have looked at Merge Sort and Quick Sort (and discussed a couple Quick Sort variations), we'd like to empirically verify what we have discussed about their relative efficiencies. We will do this by timing the algorithms as well as counting the number of comparisons and data movements of each sort in different situations on different size arrays. We will then tabulate our results and compare the algorithms' performances. We hope to see differences in the relationships between the performance metrics and array sizes for the different algorithms, and possibly come to some conclusions about which versions are best in given situations and overall.

DETAILS

You will test 9 different sorting algorithms:

1) QS1: Simple Quick Sort with A[last] as the pivot (in file Quick.java)

2) QS2: Median of 3 Quick Sort as given in TextMergeQuick.java (base case array size < 5)

3) QS3: Median of 3 Quick Sort as given in TextMergeQuick.java but with base case array size < 20

4) QS4: Median of 3 Quick Sort as given in TextMergeQuick.java, but with base case array size < 100

5) QS5: Random Pivot Quick Sort with base case array size < 5

6) QS6: Iterative Quick Sort developed by converting the recursive Quick Sort into iterative using an explicit stack

7) MS1: Recursive Merge Sort as given in TextMergeQuick.java

8) MS2: Iterative Merge Sort as given in TextMergeQuick.java

9) MS3: Iterative Merge Sort developed by converting the recursive Merge Sort into iterative using an explicit stack

The code for six algorithms (1-4 and 7-8) is already completely written you only have to change the base case value in the Median of 3 Quick Sort from a constant to a variable so that you can give it different values during your program execution. You must write the other three algorithms (5-6 and 9) so that it works correctly. Random Pivot Quick Sort is actually very similar to the simple Quick Sort, except that you choose the pivot index as a random integer between first and last (inclusive) rather than choosing it as A[last].

Your primary task in this assignment is to write a main program that will enable the user to time all 9 of the algorithms under different circumstances, and then to tabulate and analyze the resulting data.

INPUT AND VARIABLE SETUP

Your program should allow the following to be input from the user:

1) The size of the arrays to be tested.

2) The number of trials for each test. The overall performance for the test will be the average of the performance for each of the trials. For random data, each trial should have different numbers in the array, but the data for a given trial should be the same random data for all 9 algorithms. In other words, consider, for example, an array called A1, algorithms QS1 and QS2, and trials T1 and T2. If A1 is filled with random numbers for QS1 in trial T1, then those same numbers (in the same initial positions) should be used for QS2 in trial T1. However, different random numbers should be generated for trial T2, again using the same numbers for both QS1 and QS2.

3) The name of the file your results will be output to.

For each algorithm your program should iterate through 3 initial setups of the data:

a) Random in this case you will fill the arrays with random integers. To make your assessments more accurate, each of your algorithms should utilize the same random data, as mentioned above. This can be accomplished in several ways but you will lose credit if the data is not the same

b) Already sorted (low to high) in this case simply fill the arrays with successive integers starting at 1.

c) Already reverse sorted (high to low) in this case simply fill the arrays with decreasing integers starting at the array length.

Timing and Measurement: You will time your algorithms using the predefined method

System.nanoTime()

This method returns the time elapsed on the system timer in nanoseconds. You will time one trial in the following fashion:

long start = System.nanoTime();

// Execute the sorting method here (array should ALREADY be filled before timing starts)

long finish = System.nanoTime();

long delta = finish start;

Since you are performing multiple trials, for a given algorithm you will add the times for the trials together, then divide by the number of trials to get the average time per trial. You may also want to divide by 1 billion to get your final results in seconds rather than nanoseconds.

You will also need to measure the number of comparisons and the number of data movements of the algorithms. You will need to instrument your code to add performance counters to the sorting algorithms. Every time a comparison is made, you would need to increment a comparison counter. Every time an assignment is made using the array the data moves counter has to be incremented.

Since you are performing multiple trials, for a given algorithm you will add up the counters for the trials together, then divide by the number of trials to get the average per trial.

OUTPUT

For each of the variations in the run, your program must output its results to the file named by the user. Note that since you have 3 data setups and 9 algorithms, each overall execution of your main program should produce 27 different results. Each result should look something like the following example

Algorithm: Simple Quick Sort:

Array Size: 25000

Order: Random

Number of trials: 10

Average time: 0.0038441037 sec

Average number of comparisons: 579427.2 comparisons

Average number of data moves: 279606.6 data moves

Trace Output Mode: In order for your TA to be able to test the correctness of your sorting algorithms and main program logic, you are required to have a Trace Output Mode for your program. This mode should be automatically set when the Array Size is <= 20. In Trace Output Mode, your program should output all of the following to standard output (i.e., the display) for EACH trial of EACH algorithm:

Algorithm being used

Array Size

Data configuration (sorted, reverse sorted, random)

Initial data in array prior to sorting

Data in array after sorting

The evaluation of the correctness of your algorithms and data processing will be heavily based on the Trace Output Mode for your program. If you do not implement this or it does not work correctly, you will likely lose a lot of credit.

Note: Be sure that Trace Output Mode is OFF for arrays larger than 20.

RUNS

The goal is to see how the performance of the algorithms changes as the size of the arrays increases. Use 10 trials for all of your runs.

Size = 25000, Filename = test25k.txt

Size = 50000, Filename = test50k.txt

Size = 100000, Filename = test100k.txt

Note: Only do the first 3 sizes above for the Simple Quick Sort. Even with these it may take a while for the simple Quick Sort algorithm and you will have to increase the stack size of the JRE to accommodate the execution see below. For the sizes below you will only have 24 results.

Size = 200000, Filename = test200k.txt

Size = 400000, Filename = test400k.txt

Size = 800000, Filename = test800k.txt

Size = 1600000, Filename = test1600k.txt

Size = 3200000, Filename = test3200k.txt

An example run may appear as shown below:

assig4> java -Xss10m Assig4

Enter array size: 25000

Enter number of trials: 10

Enter file name: test25k.txt

An example output file is test25k.txt:

Algorithm: Simple QuickSort Array Size: 25000 Order: Random Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Median of Three (5) Array Size: 25000 Order: Random Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Median of Three (20) Array Size: 25000 Order: Random Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Median of Three (100) Array Size: 25000 Order: Random Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Random Pivot (5) Array Size: 25000 Order: Random Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Iterative Quick Sort Array Size: 25000 Order: Random Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Recursive MergeSort Array Size: 25000 Order: Random Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Iterative MergeSort Array Size: 25000 Order: Random Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Iterative MergeSort with explicit stack Array Size: 25000 Order: Random Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Simple QuickSort Array Size: 25000 Order: Sorted Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Median of Three (5) Array Size: 25000 Order: Sorted Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Median of Three (20) Array Size: 25000 Order: Sorted Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Median of Three (100) Array Size: 25000 Order: Sorted Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Sorted Pivot (5) Array Size: 25000 Order: Sorted Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Iterative Quick Sort Array Size: 25000 Order: Sorted Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Recursive MergeSort Array Size: 25000 Order: Sorted Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Iterative MergeSort Array Size: 25000 Order: Sorted Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Iterative MergeSort with explicit stack Array Size: 25000 Order: Sorted Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Simple QuickSort Array Size: 25000 Order: Reverse Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Median of Three (5) Array Size: 25000 Order: Reverse Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Median of Three (20) Array Size: 25000 Order: Reverse Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Median of Three (100) Array Size: 25000 Order: Reverse Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Reverse Pivot (5) Array Size: 25000 Order: Reverse Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Iterative Quick Sort Array Size: 25000 Order: Reverse Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Recursive MergeSort Array Size: 25000 Order: Reverse Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Iterative MergeSort Array Size: 25000 Order: Reverse Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

Algorithm: Iterative MergeSort with explicit stack Array Size: 25000 Order: Reverse Number of trials: 10 Average Time: ... sec Average number of comparisons: ... comparisons Average number of data moves: ... moves

RESULTS

After you have finished all of your runs, tabulate your results in an Excel spreadsheet. Use a different worksheet for each initial ordering (random, sorted, reverse sorted). In each worksheet, make three tables (one for time, a second for number of comparisons, and a third for number of data moves) of your results with the array sizes as the columns and the algorithms as the rows. Also make a graph for each of your tables so that you can visualize the growth of the run-time and performance metrics for each algorithm

You must also write a brief summary/discussion of your results. Based on your tables, indicate the best algorithm for each of the initial data orderings. Based on your overall results (for all data orderings), speculate on what you think the best of the 9 algorithms is for general purpose use. Your write-up should be well written and justified by your results. Your write-up can be embedded in your spreadsheet or submitted as a separate document (e.g., a Word document).

ADDITIONAL REQUIREMENTS, HINTS AND HELP

For help with generating random integers, see the Random class in the Java API and specifically the nextInt() method.

To make your results more accurate, do not run anything else on your machine while you are doing your runs. Don't worry about system processes that are running just make sure you don't run any other applications.

To make your results consistent, do all of your runs on the same machine under the same (if possible) circumstances.

Note that for smaller arrays and in some cases even for larger arrays the time for a given trial may be very small perhaps even negligible.

Be sure to time only the actual sorting procedure do not time loading the data into the array or any I/O, such as printing to the screen or reading from the keyboard; this is very slow and will skew the timing greatly)

As we discussed, in some cases a recursive algorithm makes so many calls that it uses up all of the memory in the run-time stack, causing the JRE to crash. To prevent this problem we can invoke the Java interpreter with a flag to indicate the size of the run-time stack. This can be done in the following way: prompt> java Xss MainClassName

You may have to experiment with the value for to avoid getting a StackOverflowError, but in my runs using 10M worked. If you think about how these algorithms execute, you will see that we only have to worry about the stack size for the Simple Quick Sort algorithm in the cases of the sorted and reverse sorted data.

Extra CREDIT

For comparison purposes, add some additional sorting algorithms to your tests to see how they compare. For example, you could include Shellsort or Insertionsort.

Provided Code:

TextMergeQuick

public class TextMergeQuick

{

public static final int MIN_SIZE = 5; // for quick sort

// MERGE SORT

public static >

void mergeSort(T[] a, int n)

{

mergeSort(a, 0, n - 1);

} // end mergeSort

public static >

void mergeSort(T[] a, int first, int last)

{

@SuppressWarnings("unchecked")

T[] tempArray = (T[])new Comparable[a.length];

mergeSort(a, tempArray, first, last);

} // end mergeSort

private static >

void mergeSort(T[] a, T[] tempArray, int first, int last)

{

if (first < last)

{ // sort each half

int mid = (first + last)/2;// index of midpoint

mergeSort(a, tempArray, first, mid); // sort left half array[first..mid]

mergeSort(a, tempArray, mid + 1, last); // sort right half array[mid+1..last]

if (a[mid].compareTo(a[mid + 1]) > 0) // Question 2, Chapter 9

merge(a, tempArray, first, mid, last); // merge the two halves

// else skip merge step

} // end if

} // end mergeSort

private static >

void merge(T[] a, T[] tempArray, int first, int mid, int last)

{

// Two adjacent subarrays are a[beginHalf1..endHalf1] and a[beginHalf2..endHalf2].

int beginHalf1 = first;

int endHalf1 = mid;

int beginHalf2 = mid + 1;

int endHalf2 = last;

// while both subarrays are not empty, copy the

// smaller item into the temporary array

int index = beginHalf1; // next available location in

// tempArray

for (; (beginHalf1 <= endHalf1) && (beginHalf2 <= endHalf2); index++)

{ // Invariant: tempArray[beginHalf1..index-1] is in order

if (a[beginHalf1].compareTo(a[beginHalf2]) <= 0)

{

tempArray[index] = a[beginHalf1];

beginHalf1++;

}

else

{

tempArray[index] = a[beginHalf2];

beginHalf2++;

} // end if

} // end for

// finish off the nonempty subarray

// finish off the first subarray, if necessary

for (; beginHalf1 <= endHalf1; beginHalf1++, index++)

// Invariant: tempArray[beginHalf1..index-1] is in order

tempArray[index] = a[beginHalf1];

// finish off the second subarray, if necessary

for (; beginHalf2 <= endHalf2; beginHalf2++, index++)

// Invariant: tempa[beginHalf1..index-1] is in order

tempArray[index] = a[beginHalf2];

// copy the result back into the original array

for (index = first; index <= last; index++)

a[index] = tempArray[index];

Quick

public class Quick

{

public static >

void quickSort(T[] array, int n)

{

quickSort(array, 0, n-1);

} // end quickSort

public static >

void quickSort(T[] array, int first, int last)

{

if (first < last)

{

// create the partition: Smaller | Pivot | Larger

int pivotIndex = partition(array, first, last);

// sort subarrays Smaller and Larger

quickSort(array, first, pivotIndex-1);

quickSort(array, pivotIndex+1, last);

} // end if

} // end quickSort

private static >

int partition(T[] a, int first, int last)

{

int pivotIndex = last; // simply pick pivot as rightmost element

T pivot = a[pivotIndex];

// determine subarrays Smaller = a[first..endSmaller]

// and Larger = a[endSmaller+1..last-1]

// such that elements in Smaller are <= pivot and

// elements in Larger are >= pivot; initially, these subarrays are empty

int indexFromLeft = first;

int indexFromRight = last - 1;

boolean done = false;

while (!done)

{

// starting at beginning of array, leave elements that are < pivot;

// locate first element that is >= pivot

while (a[indexFromLeft].compareTo(pivot) < 0)

indexFromLeft++;

// starting at end of array, leave elements that are > pivot;

// locate first element that is <= pivot

while (a[indexFromRight].compareTo(pivot) > 0 && indexFromRight > first)

indexFromRight--;

// Assertion: a[indexFromLeft] >= pivot and

// a[indexFromRight] <= pivot.

if (indexFromLeft < indexFromRight)

{

swap(a, indexFromLeft, indexFromRight);

indexFromLeft++;

indexFromRight--;

}

else

done = true;

} // end while

// place pivot between Smaller and Larger subarrays

swap(a, pivotIndex, indexFromLeft);

pivotIndex = indexFromLeft;

// Assertion:

// Smaller = a[first..pivotIndex-1]

// Pivot = a[pivotIndex]

// Larger = a[pivotIndex + 1..last]

return pivotIndex;

} // end partition

private static void swap(Object [] a, int i, int j)

{

Object temp = a[i];

a[i] = a[j];

a[j] = temp;

} // end swap

}

If you need anything else let me know, thank you very much!!!!!