Question
yyou 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
yyou 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 mergingpairs of sub-arrays into a temporary array and then copying the merged array of double size back into theoriginal place in the input array at the end of each merging phase. Please write your implementation in a waythat avoids this back copying (you still need the temporary array though). (Hint: implement the merge-sortwithout 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: 1.Sorted arrays (in the increasing order, so the array will be unchanged after the execution of each method) 2.Reverse-sorted arrays 3.Randomly generated input arrays (you can find libraries to generate random integers in Java). Sincerandom arrays may result in some corner cases in terms of algorithm performance, and also becauserunning the same program even on the same input can take different time due to random scheduling andparallel activities, obtain each measurement in this step multiple times (e.g., 10 times) using differentrandomly generated arrays each time (use different seeds for your random number generators) and use theaverages and variances of all your measurements for this step in your report. This is useful to show thatyour results are not a function of some lucky input data. 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; thats 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. The "Reporting1" program generates all your arrays for sorting, runs each of the sorting methods as many times as specified in the assignment, giving them the arrays as arguments, records the execution time of these methods, prints out the results in a form suitable for inclusion into your report and/or writes out the results into a file if you need to post-process your results (e.g., by Excel to produce some graphs for your report). If you do not need this output file for your report, you do not have to write it. If you do produce all your results in their final form from the Reporting1 program (rather than writing them out for excel post-processing), you will need to compute a variance within your Reporting1 program. This is actually straightforward. In case someone has not yet taken a statistics class, if you have a sample of n measurements of a random quantity X (x1, , xn,) then the variance V is computed as follows:
where x- is the mean (average) value of the sample x1, , xn. So, its a simple loop to compute this in your java program. Please have two helper methods: double meanVal(int arrayOfSamples) and double varianceVal(int arrayOfSamples, double mean). The meanVal method accepts the array of samples (in your case it will be 10 values) and returns the mean value of the samples. The varianceVal method accepts the array of samples and returns the variance. The Reporting2 program is to test your implementation of the sorting methods. We will be testing your work by typing java Reporting2
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started