In this assignment, you will implement and study the performance of three sorting algorithms: heap-sort, quick-sort, and merge-sort. Each method below takes as arguments an integer array, which then becomes sorted in the increasing order of elements void heapSort(int [] arr) * void quickSort(int [] arr). (Include your pivot-selection technique into this method.) void mergeSort(int [] arr). Note: Our implementation of merge-sort in the lecture notes involved merging pairs of sub-arrays into a temporary array and then copying the merged array of double size back into the original place in the input array at the end of each merging phase. Please write your implementation in a way that avoids this back copying (you still need the temporary array though). (Hint: implement the merge-sort without recursion, taking care of the arrays whose size is not a power of two.) Please make these methods static and organize them into a Sorting class (as you would often do with utility functions - we discussed this in class when we started our module on sorting). After implementing the methods and testing them for correctness, your research begins. You need to write a test program to obtain the running times of the three methods, and compare them (see below some tips on measuring running time of your code). Perform your comparison on the following arrays Sorted arrays (in the increasing order, so the array will be unchanged after the execution of each method) Reverse-sorted arrays Randomly generated input arrays (you can find libraries to generate random integers in Java). Since random arrays may result in some corner cases in terms of algorithm performance, and also because running the same program even on the same input can take different time due to random scheduling and parallel activities, obtain each measurement in this step multiple times (e.g., 10 times) using different randomly generated arrays each time (use different seeds for your random number generators) and use the averages and variances of all your measurements for this step in your report. This is useful to show that your results are not a function of some lucky input data 1. 2. 3. The size of input array should be varied in a wide range, for example, measure your executions for arrays of size 1000, 10,000, 100,000, 1,000,000. Please investigate the comparative performance as you vary the size of the input Note that while repeating your measurements for different random arrays in step 3 will take care of any skew both from corner-case input and from random program scheduling, you should take repeated runs over the same array in steps 1 and 2. In these two steps, just repeating each run 3 times and taking the median running time will eliminate many outlier measurements. You can see how quickly collecting measurements becomes too tedious to do manually; that's why we normally write special testing scripts and programs that automate these tasks - as you should in this assignment to get full credit. Specifically, you should have, in your deliverables, two classes with "main" functions: Reporting1.java and Reporting2.java. Please also include them in the compiled form: Reporting1.class and Reporting2.class. In this assignment, you will implement and study the performance of three sorting algorithms: heap-sort, quick-sort, and merge-sort. Each method below takes as arguments an integer array, which then becomes sorted in the increasing order of elements void heapSort(int [] arr) * void quickSort(int [] arr). (Include your pivot-selection technique into this method.) void mergeSort(int [] arr). Note: Our implementation of merge-sort in the lecture notes involved merging pairs of sub-arrays into a temporary array and then copying the merged array of double size back into the original place in the input array at the end of each merging phase. Please write your implementation in a way that avoids this back copying (you still need the temporary array though). (Hint: implement the merge-sort without recursion, taking care of the arrays whose size is not a power of two.) Please make these methods static and organize them into a Sorting class (as you would often do with utility functions - we discussed this in class when we started our module on sorting). After implementing the methods and testing them for correctness, your research begins. You need to write a test program to obtain the running times of the three methods, and compare them (see below some tips on measuring running time of your code). Perform your comparison on the following arrays Sorted arrays (in the increasing order, so the array will be unchanged after the execution of each method) Reverse-sorted arrays Randomly generated input arrays (you can find libraries to generate random integers in Java). Since random arrays may result in some corner cases in terms of algorithm performance, and also because running the same program even on the same input can take different time due to random scheduling and parallel activities, obtain each measurement in this step multiple times (e.g., 10 times) using different randomly generated arrays each time (use different seeds for your random number generators) and use the averages and variances of all your measurements for this step in your report. This is useful to show that your results are not a function of some lucky input data 1. 2. 3. The size of input array should be varied in a wide range, for example, measure your executions for arrays of size 1000, 10,000, 100,000, 1,000,000. Please investigate the comparative performance as you vary the size of the input Note that while repeating your measurements for different random arrays in step 3 will take care of any skew both from corner-case input and from random program scheduling, you should take repeated runs over the same array in steps 1 and 2. In these two steps, just repeating each run 3 times and taking the median running time will eliminate many outlier measurements. You can see how quickly collecting measurements becomes too tedious to do manually; that's why we normally write special testing scripts and programs that automate these tasks - as you should in this assignment to get full credit. Specifically, you should have, in your deliverables, two classes with "main" functions: Reporting1.java and Reporting2.java. Please also include them in the compiled form: Reporting1.class and Reporting2.class
