Due by 11:59pm Wednesday, April 3
For this assignment, download the folder assign9.zip and use the file Sort.java in the folder as your starting point. This version of Sort.java contains test cases and starting code for the exercises below.
Finish the implementation of Quicksort from Lab 9 (exercise 7). You can test your Quicksort implementation by running the commands:
> java Sort quick > java Sort quick 200
Complete the implementation of countSort1 and countSort2 from Lab 9 (exercises 8 and 10). IMPORTANT: when testing countSort1 and countSort2, make sure to first uncomment the appropriate line in the generateTestCase method of Sort, and then recompile Sort. This will ensure that the random data arrays generated for testing have the right properties for the algorithm.
The countSort1 algorithm has O(n) time complexity, where n is the length of the data array. What is the big-O time complexity of countSort2? Why? Include a clear explanation in a comment in your code.
Complete the implementation of mergeSort2, a new version of Mergesort that uses only O(n) space instead of O(n log n) space. Instead of creating brand new smaller arrays every time the method is called recursively (as mergeSort does), mergeSort2 creates a single workspace array equal in size to the array to be sorted. The auxiliary method mergeArrays2 assumes that the elements in the subregions data[first ... mid] and data[mid+1 ... last] are already sorted, and merges them together into the subregion data[first ... last], using the workspace array as "scratch space". You can test your code by running the command:
> java Sort merge2
You should finish the other problems first before attempting these.
Generalize countSort further so that it works for arbitrary arrays of integers (possibly including negative values), by completing the countSort3 method in Sort. To test countSort3, uncomment the appropriate line in generateTestCase, recompile Sort, and run the commands below a few times. What is the time complexity of countSort3? What is its space complexity? Include your answers in a comment in your code.
> java Sort count3 > java Sort count3 200
Implement the following modification of the Quicksort algorithm (due to Bentley and McIlroy), by completing the choosePivot2 method in Sort. The only difference between quickSort2 and quickSort is the way the pivot value is chosen. Instead of using the first element as the pivot, we use an approximation of the median. (The median of three values a ≤ b ≤ c is b.) If the array size n ≤ 7, use the middle element of the array. If n ≤ 40, use the median of the first, middle, and last element. Otherwise compute the "pseudomedian" of the nine elements data[i*(n-1)/8], where i ranges from 0 to 8. The pseudomedian of nine values is the median of median(v0, v1, v2), median(v3, v4, v5), and median(v6, v7, v8).
Compare the running time of this modification with that of the original algorithm on sequences that are nearly-sorted or reverse-sorted, and on sequences with many identical elements. What do you observe? Hint: To test quickSort2 on various types of arrays, uncomment the appropriate lines in generateTestCase and recompile Sort. You can test quickSort2 with the command:
> java Sort quick2
Files to submit:
Submit the above file using the Homework Upload Site. Please include your name and the assignment number in a comment at the top of the file. You DO NOT need to submit Arraytools.java, SortBase.java, SortTimer.java, Stopwatch.java, or any of your compiled .class files.
If you have questions about anything, just ask!