This project is an extension of project 1. I will provide all the codes of project 1 here. Please let me know if anything else is needed. Thank you

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 oA 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.

BenchMarkSorts.java

import java.util.Arrays; import java.util.Random;

public class BenchmarkSorts { int [] list; int iterativeCount = 0; int recursiveCount = 0; long iterativeTime, recursiveTime; int [] iterativeCountLog = new int [50]; int [] recursiveCountLog = new int [50]; int a = 0; int b = 0; long [] iterativeTimeLog = new long[50]; long []recursiveTimeLog = new long[50]; int n; YourSort mySort = new YourSort(); public BenchmarkSorts (int[] sizes)throws Exception{ for (int a = 0; a < sizes.length; a++){ n = sizes[a]; BenchmarkSorts bSort = new BenchmarkSorts(n); }

} private BenchmarkSorts (int n) throws Exception{ for (int i = 1; i < 50; i++){ list = new int [n]; for (int j = 0; j < n; j++){ Random val = new Random(); list[j] = (val.nextInt(1001)); } runSorts(); } displayReport(n); }

public void runSorts() throws Exception{ int [] tempArray1 = list; int [] tempArray2 = list; mySort.iterativeSort(tempArray1); int returnCount = mySort.getCount(); long returnTime = mySort.getTime(); iterativeCount = iterativeCount + returnCount; iterativeTime = iterativeTime + returnTime; iterativeCountLog[a] = returnCount; iterativeTimeLog[a] = returnTime; a++; mySort.recursiveSort(tempArray2); returnCount = mySort.getCount(); returnTime = mySort.getTime(); recursiveCount = recursiveCount + returnCount; recursiveTime = recursiveTime + returnTime; recursiveCountLog[b] = recursiveCount; recursiveTimeLog[b] = recursiveTime; b++; } public void displayReport(int n){ double iterativeAverageCount = 0; double iterativeAverageTime = 0; double recursiveAverageCount = 0; double recursiveAverageTime = 0; double iterativeSDCount = 0; double iterativeSDTime = 0; double recursiveSDCount = 0; double recursiveSDTime = 0; iterativeAverageCount = iterativeCount / 49; iterativeAverageTime = iterativeTime / 49; recursiveAverageCount = recursiveCount / 49; recursiveAverageTime = recursiveTime / 49; for (int i = 1; i < 50; i++){ iterativeSDCount = iterativeSDCount + Math.pow((iterativeCountLog[i] - iterativeAverageCount), 2); iterativeSDTime = iterativeSDTime + Math.pow((iterativeTimeLog[i] - iterativeAverageTime), 2); recursiveSDCount = recursiveSDCount + Math.pow((recursiveCountLog[i] - recursiveAverageCount), 2); recursiveSDTime = recursiveSDTime + Math.pow((recursiveTimeLog[i] - recursiveAverageTime), 2); } iterativeSDCount = Math.pow(iterativeSDCount, .5) / n; iterativeSDTime = Math.pow(iterativeSDTime, .5) / n; recursiveSDCount = Math.pow(recursiveSDCount, .5) / n; recursiveSDTime = Math.pow(recursiveSDTime, .5) / n; System.out.println("Iterative Selection Sort Results: " + " Data Set Size (n): " + n + ", Average Critical Operation Count: " + iterativeAverageCount + ", Standard Deviation of Count: " + iterativeSDCount + ", Average Execution Time: " + iterativeAverageTime + ", Standard Deviation of Time: " + iterativeSDTime); System.out.println("Recursive Selection Sort Results: " + " Data Set Size (n): " + n + ", Average Critical Operation Count: " + recursiveAverageCount + ", Standard Deviation of Count: " + recursiveSDCount + ", Average Execution Time: " + recursiveAverageTime + ", Standard Deviation of Time: " + recursiveSDTime); } }

SortInterface.java

public interface SortInterface { void iterativeSort (int [] list) throws Exception; void recursiveSort (int [] list) throws Exception; public int getCount(); public long getTime(); }

SortMain.java

public class SortMain {

/** * @param args the command line arguments */ public static void main(String[] args) throws Exception{ int[] sizes = {100, 200, 300, 400, 500, 600, 700, 800, 900, 1000} ; BenchmarkSorts bSorts = new BenchmarkSorts(sizes); } }

UnsortedException.java

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

YourSort.java

public class YourSort implements SortInterface{ public UnsortedException unsorted; int iterativeCount; int recursiveCount; long iterativeTime; long recursiveTime; // long [] times; // int [] counts; //iterative selection sort method, modified from Liang Listing 6.8 public void iterativeSort (int [] list) throws Exception { iterativeCount = 0; long startTime = System.nanoTime(); for (int i = 0; i < list.length - 1; i++){ //find the minimum in the list [i..n] int currentMin = list[i]; int currentMinIndex = i; for (int j = i + 1; j < list.length; j++){ if (currentMin > list[j]){ currentMin = list[j]; currentMinIndex = j; } iterativeCount++; } //swap list [i] with list [currentMinIndex] if necessary if (currentMinIndex != i){ list[currentMinIndex] = list[i]; list[i] = currentMin; } // iterativeCount++; } long endTime = System.nanoTime(); iterativeTime = endTime - startTime; for (int i = 0; i < list.length - 1; i++){ if (list[i] > list [i + 1]){ unsorted = new UnsortedException ("Sort failed!"); throw unsorted; } } } //recursive selection sort method from Liang listing 20.5 public void recursiveSort(int [] list) throws Exception { recursiveCount = 0; recursiveSort(list, 0, list.length - 1); } public void recursiveSort(int [] list, int low, int high)throws Exception{ long startTime = System.nanoTime(); if (low < high) { //find the smallest number and its index in list [low...high] int indexOfMin = low; int min = list[low]; for (int i = low + 1; i <= high; i++){ if (list[i] < min) { min = list[i]; indexOfMin = i; } recursiveCount++; } //swap the smallest in list [low...high] with list [low] list[indexOfMin] = list[low]; list[low] = min; // recursiveCount++; //sort the remaining list [low+1...high] recursiveSort(list, low + 1, high); // recursiveCount++; } long endTime = System.nanoTime(); recursiveTime = endTime - startTime; for (int i = 0; i < list.length - 1; i++){ if (list[i] > list [i + 1]){ unsorted = new UnsortedException ("Sort failed!"); throw unsorted; } } } public int getCount(){ int totalCount = iterativeCount + recursiveCount; iterativeCount = 0; recursiveCount = 0; return totalCount; } public long getTime(){ long totalTime = iterativeTime + recursiveTime; iterativeTime = 0; recursiveTime = 0; return totalTime; } }