Project 2 involves writing an analysis of the results that you obtained in first project. You are to submit a paper that discusses the results of your analysis. Your paper should include the following items:

? A brief introduction of the sorting algorithm that you have selected and how the two versions of the algorithm compare including:

o High-level pseudocode for the sorting algorithms

o A Big-? analysis of the two versions of the algorithm

o An explanation of your approach to avoiding the problems associated with JVM warm-up

o A discussion of the critical operation that you chose to count with an explanation of why you selected it

? An analysis of the results of your study, which should include:

o graph of critical operations for both algorithms and one for the execution times

o a comparison of the performance of the two versions of the algorithm

o a comparison of the critical operation results and the actual execution time measurements

o a discussion of the significance of the coefficient of variance results and how it reflects the data sensitivity of your algorithm

o how your results compare to your Big-? analysis

? A conclusion that summarizes the important observations of your study If for any reason, it was necessary to revise the program you submitted in project 1, the revised source code should also be included along with the paper.

Code:

BenchmarkSorts.java

import java.util.Random; import java.util.stream.IntStream;

public class BenchmarkSorts {

private final int NUMBER_OF_RUNS = 50;

private int[] array; private int[] sortedIterativeArray; private int[] sortedRecursiveArray; private int iterativeCount = 0; private int recursiveCount = 0; private int iterativeIndex = 0; private int recursiveIndex = 0; private long iterativeTime, recursiveTime; private int [] iterativeCountLog = new int[NUMBER_OF_RUNS]; private int [] recursiveCountLog = new int[NUMBER_OF_RUNS]; private long [] iterativeTimeLog = new long[NUMBER_OF_RUNS]; private long []recursiveTimeLog = new long[NUMBER_OF_RUNS];

private MergeSort mergeSort = new MergeSort();

public BenchmarkSorts(int[] sizes) {

// Creates benchmarks based on the input array size IntStream.range(0, sizes.length).forEach(i -> new BenchmarkSorts(sizes[i])); }

private BenchmarkSorts(int n) {

// Outer loop 50 times (NUMBER_OF_RUNS) IntStream.range(0, NUMBER_OF_RUNS).forEach(i -> { array = new int[n]; // Inner loop based on the array size (n) IntStream.range(0, n).forEach(j -> { Random random = new Random(); array[j] = random.nextInt(1000); });

// Runs the sort and produces output if an UnsortedException is found try { runSorts(); } catch (UnsortedException e) { System.out.println(e.getMessage()); } }); displayReport(n); }

private void runSorts() throws UnsortedException {

// Runs iterative sort sortedIterativeArray = mergeSort.iterativeSort(array); int returnCount = mergeSort.getCount(); long returnTime = mergeSort.getTime(); iterativeCount = iterativeCount + returnCount; iterativeTime = iterativeTime + returnTime; iterativeCountLog[iterativeIndex] = returnCount; iterativeTimeLog[iterativeIndex] = returnTime; iterativeIndex++;

// Runs recursive sort sortedRecursiveArray = mergeSort.recursiveSort(array); returnCount = mergeSort.getCount(); returnTime = mergeSort.getTime(); recursiveCount = recursiveCount + returnCount; recursiveTime = recursiveTime + returnTime; recursiveCountLog[recursiveIndex] = recursiveCount; recursiveTimeLog[recursiveIndex] = recursiveTime; recursiveIndex++; }

private void displayReport(int arraySize) {

// Sets local variables double iterativeAverageCount = 0; double iterativeAverageTime = 0; double recursiveAverageCount = 0; double recursiveAverageTime = 0; double iterativeVarianceCount = 0; double iterativeVarianceTime = 0; double recursiveVarianceCount = 0; double recursiveVarianceTime = 0; double iterativeSDCount = 0; double iterativeSDTime = 0; double recursiveSDCount = 0; double recursiveSDTime = 0;

// Calculates averages for (int i = 0; i < NUMBER_OF_RUNS; i++) { iterativeAverageCount += iterativeCountLog[i]; iterativeAverageTime += iterativeTimeLog[i]; recursiveAverageCount += recursiveCountLog[i]; recursiveAverageTime += recursiveTimeLog[i]; }

iterativeAverageCount = iterativeAverageCount / arraySize; iterativeAverageTime = iterativeAverageTime / arraySize; recursiveAverageCount = recursiveAverageCount / arraySize; recursiveAverageTime = recursiveAverageTime / arraySize;

// Calculates standard deviations for (int i = 0; i < NUMBER_OF_RUNS; i++) { iterativeVarianceCount += Math.pow(iterativeAverageCount - iterativeCountLog[i], 2); iterativeVarianceTime += Math.pow(iterativeAverageTime - iterativeTimeLog[i], 2); recursiveVarianceCount += Math.pow(recursiveAverageCount - recursiveCountLog[i], 2); recursiveVarianceTime += Math.pow(recursiveAverageTime - recursiveTimeLog[i], 2); }

iterativeVarianceCount = iterativeVarianceCount / arraySize; iterativeVarianceTime = iterativeVarianceTime / arraySize; recursiveVarianceCount = recursiveVarianceCount / arraySize; recursiveVarianceTime = recursiveVarianceTime / arraySize;

iterativeSDCount = Math.sqrt(iterativeVarianceCount); iterativeSDTime = Math.sqrt(iterativeVarianceTime); recursiveSDCount = Math.sqrt(recursiveVarianceCount); recursiveSDTime = Math.sqrt(recursiveVarianceTime);

// Produces output System.out.println("Data Set Size (n): " + arraySize + " \tIterative Selection Sort Results: \t\t\t\t\tRecursive Selection Sort Results:" + " \tAverage Critical Operation Count: " + Math.round(iterativeAverageCount) + "\t\t\tAverage Critical Operation Count: " + Math.round(recursiveAverageCount) + " \tStandard Deviation of Count: " + Math.round(iterativeSDCount) + "\t\t\t\t\tStandard Deviation of Count: " + Math.round(recursiveSDCount) + " \tAverage Execution Time: " + Math.round(iterativeAverageTime) + "\t\t\t\t\t\tAverage Execution Time: " + Math.round(recursiveAverageTime) + " \tStandard Deviation of Time: " + Math.round(iterativeSDTime) + "\t\t\t\t\t\tStandard Deviation of Time: " + Math.round(recursiveSDTime)); } }

MergeSort.java

public class MergeSort implements SortInterface {

int count = 0; long timeStart = 0; long timeEnd = 0;

///////////////////////////////////////// // Iterative mergeSort /////////////////////////////////////////

public int[] iterativeSort(int[] a) throws UnsortedException { count++; timeStart = System.nanoTime(); int[] aux = new int[a.length]; for (int blockSize = 1; blockSize < a.length; blockSize *= 2) { count++; for (int start = 0; start < a.length; start += 2 * blockSize) { merge(a, aux, start, start + blockSize, start + 2 * blockSize); } }

timeEnd = System.nanoTime(); checkSortedArray(aux); return aux; }

private void merge(int[] a, int[] aux, int lo, int mid, int hi) { count++; // DK: add two tests to first verify "mid" and "hi" are in range if (mid >= a.length) { count++; return; }

if (hi > a.length) { count++; hi = a.length; }

int i = lo, j = mid;

for (int k = lo; k < hi; k++) { count++; if (i == mid) { count++; aux[k] = a[j++]; } else if (j == hi) { count++; aux[k] = a[i++]; } else if (a[j] < a[i]) { count++; aux[k] = a[j++]; } else { count++; aux[k] = a[i++]; } }

// copy back for (int k = lo; k < hi; k++) { count++; a[k] = aux[k]; } }

private void recursiveSort(int[] a, int[] aux, int lo, int hi) { count++; // base case if (hi - lo <= 1) { count++; return; }

// sort each half, recursively int mid = lo + (hi - lo) / 2;

recursiveSort(a, aux, lo, mid);

recursiveSort(a, aux, mid, hi);

// merge back together merge(a, aux, lo, mid, hi); }

public int[] recursiveSort(int[] a) throws UnsortedException { count++; timeStart = System.nanoTime(); int n = a.length;

int[] aux = new int[n];

recursiveSort(a, aux, 0, n);

timeEnd = System.nanoTime(); checkSortedArray(aux);

return aux; }

public int getCount() { int result = count; count = 0; return result; }

public long getTime() { long time = timeEnd - timeStart; timeEnd = 0; timeStart = 0; return time; }

private void checkSortedArray(int[] list) throws UnsortedException { for (int i = 0; i < list.length - 1; i++) { if (list[i] > list[i + 1]) { for (int j = 0; i < list.length - 1; j++) { System.out.println(" " + list[j]); } throw new UnsortedException("The array was not sorted correctly: " + list[i] + " at index " + i + " and " + list[i + 1] + " at index " + (i + 1)); } } }

}

SortInterface.java

public interface SortInterface {

int[] iterativeSort(int[] array) throws UnsortedException; int[] recursiveSort(int[] array) throws UnsortedException;

int getCount(); long getTime(); }

SortMain.java

public class SortMain {

public static void main(String[] args) throws Exception { int[] sizes = {50, 100, 500, 1000, 5000, 10000, 50000, 100000, 500000, 1000000}; new BenchmarkSorts(sizes); } }