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

Using the source code of

Benchmark Sorts

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)); } }

Merge Sort

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)); } } } }

Sort Interface

public interface SortInterface { int[] iterativeSort(int[] array) throws UnsortedException; int[] recursiveSort(int[] array) throws UnsortedException; int getCount(); long getTime(); }

Sort Main

public class SortMain { public static void main(String[] args) throws Exception { int[] sizes = {100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 15000, 20000, 50000}; new BenchmarkSorts(sizes); } }

Unsorted Exception

public class UnsortedException extends Exception { public UnsortedException(String message) { super(message); } }