Quicksort

2. Quicksort – Optimized version of Quicksort Learning objectives: Show understanding of quicksort, a commonly used sorting algorithm Collect and analyze empirical data about the performance of a program The textbook web site supplies QuickX.java (Links to an external site.), which is an optimized version of the QuickSort algorithm (pages 289-301 of the textbook) for arrays that has the following changes: Pivot: Median-of-three partitioning (see p. 296 of the textbook): Pick the median of a[left], a[center], and a[right] of the subarray to be the pivot (or the median of any three random elements in the subarray). Cutoff to insertion sort (see p. 296 of the textbook) for subarrays with less than M elements. The existing code uses M = 8. In this problem, you will experiment with different values of M. You have two tasks: 1. Random pivot: Change the quicksort algorithm in this class to randomly pick an element in the array to be the pivot. You will do this by changing the partition() method, but be sure to change it in a way that makes it easy to switch back and forth between median-of-three partitioning and random pivot. You need to add the following method: // Returns the index of a pivot in the subarray a[lo..hi]. int randomPivot(Comparable[] a, int lo, int hi) partition() calls getPivot(), which in turn calls randomPivot() if USE_RANDOM_PIVOT is true. Empirically determine which strategy -- random pivot or median-of-3 partitioning -- runs fastest in your environment to sort random arrays of N Doubles, for N = 103, 104, 105, and 106. This means you have to write code to generate those random arrays and to time the results. You can use the Stopwatch class (part of the textbook code) for this. 2. Testing values of M: Empirically determine the value M for which each version of quicksort (each strategy for choosing the pivot) runs fastest in your environment to sort random arrays of N Doubles, for N = 103, 104, 105, and 106. You can do this by changing the value of the INSERTION_SORT_CUTOFF instance variable (since you are testing 30 different values of M, that's a good hint that you should write a loop that tests these different values, rather than changing INSERTION_SORT_CUTOFF by hand). Test values of M between 0 and 30. You can use the Stopwatch class (part of the textbook code) to time your code. For each value of N, plot the average running times for M from 0 to 30 using a scatter plot (use Excel, Google Sheets, or any other software for making charts; don't draw it by hand.) Clarifications added 4/17/2020: No unit tests are necessary for this problem, since you are testing performance and can assume your code is correct. See Using the textbook code as a starting point for how to time your code. Clarification added 4/9/2020: How you export the data into Excel is up to you, but the way I would do it is to have your code print out one line for each value of M, then copy-and-paste the output into a spreadsheet. An example of how your code's output might look: 0 0.1 1 0.0582 2 0.00322 3 0.000345 This means that when M = 0, the running time is 0.1 seconds; when M = 1, the running time is 0.0582 seconds; etc. (These numbers are made up, so don't be alarmed if your running times are very different.) When you copy and paste output that looks like this, you'll get two columns, one for the values of M and one for the values of the running time. That makes it easy to create a chart where the running time is the dependent variable (y value) and the value of M is the independent variable (x value). Getting started: In Eclipse: Right-click on the "Lab2" icon in the left sidebar. Select "Build Path" from the pop-up menu, then select "Add Libraries..." from the second menu that pops up. Make sure "JRE System Library" is selected (highlighted). Click Next. Click Finish. Right-click on the "Lab2Part2" folder underneath the "Lab2" icon. In the menu that pops up, select "Build Path", then select "Use as source folder" from the second menu that pops up. To run the code, right-click on the "QuickSort.java" icon in the sidebar and select "Run As", then "Java application" from the second menu that pops up. You can also go to the Run menu > "Run As" > "Java application". You will see an assertion failure, which is expected. Start editing the code to make the test work! Alternately, or if you're not using Eclipse: https://github.com/catamorphism/cis27/tree/master/Lab2/Part2 (Links to an external site.) and copy/paste the Java file there into your project. You will need to import the textbook code (see Using the textbook code ).