This is just a repository where I store all the projects for my algorithms class (2016 fall.) with Prof. Hantao Zhang.
CS:3330 Algorithms Project 2: Due 10/26/2016
Task 1: For a recursive call, if the size of a subarray is less than 32, use insertion sort instead. Suppose merge sort and quick sort with this idea are implemented in methods called mergesort2 and quicksort2. Create a method called task1, which compares the performances of four methods, i.e., mergesort, mergesort2, quicksort, and quicksort2, on the same set of 100 random arrays of size 10,000,000. The method task1 will create these 100 examples and summerize the running time for each method. Based on the experimental results, draw your conclusions.
Task 2: For many inputs, testing if a subarray is already sorted can also speed up quicksort. In this task, please implement the following method which checks if the subarray of the array arr (from low to high, inclusive) is already sorted: private static boolean isSorted(int low, int high) Using isSorted(low, high) in quicksort as follows: At the beginning of the recursive call, check if the subarray is already sorted. If yes, exit doing nothing; otherwise, continue as usual. Let us call the method using this idea quicksort3. Please create a method called task2, which compares the performances of three methods, i.e., quicksort, quicksort2, and quicksort3, on the same set of 10 random arrays of size 10,000,000, plus 10 copies of sorted and reversely sorted arrays of size 10,000,000. The method task2 will create these examples and summerize the running time for each method. Based on the experimental results, draw your conclusions.
Task 3: It is known that the qualify of pivots in quicksort affects the performance of quicksort. Please experiment these two ideas in quicksort: One uses the median of three elements, i.e., first, middle, and last, as pivot for partition. One first selects 9 elements equally spreading out in the array, inclduing the first and the last element. Compute the median of the first three, the median of the next three, and the median of the last three. Then use the median of three medians as pivot. Based on the best quicksort method from Task 1 and Task 2, create two new methods, called quicksort4 and quicksort5, such that quicksort4 uses the first idea and quicksort5 uses the second idea. Please create a method called task3, which compares the performances of six methods, i.e., heapsort, quicksort, quicksort3, quicksort4, quicksort5, and natural mergesort, on the same set of arrays of size 1,000,000, including 10 copies random arrays, 10 copies of reversely sorted arrays, and 10 copies of organ-pipe shaped inputs (the first half is from n/2 downto 1 and the second half from 1 to n/2, where n is the size of the array). The method task3 will create these examples and summerize the running time for each method. Based on the experimental results, draw your conclusions. On www.sorting-algorithms.com, the illustration shows that heapsort is often the winner for reversely sorted arrays. Do you agree or disagree? Draw your conclusion with justification.
Task 4: On www.sorting-algorithms.com, it says that "insertion sort is the clear winner" on nearly sorted arrays. There are at least two types of "nearly sorted" arrays: k-exchanges and k-distance, where k is an integer. An array is called a k-exchanges array if the array becomes sorted by performing at most k exchanges. For example, sorting.java uses 100-exchanges for nearly sorted arrays. An array is called a k-distance array if, for each element, the distance from its initial position to its position in the sorted array is no more than k. A k-distance array can be created from a sorted array by randomly shuffling each subarray of size k. www.sorting-algorithms.com uses 1-distance for nearly sorted arrays. Please compare the performances of quicksort (choosing the best quicksort you have), heapsort, mergesort, natural mergesort, and insertion sort on k-exchanges and k-distances arrays for various k values. You will create a method called task4, which takes k = 10, 20, 30, ..., until quicksort becomes a clear winner, create 100 k-distance arrays of size 10,000,000, run in turn the chosen sorting methods on each array, and collect running times. Then for k = 100, 200, 300, ..., until quicksort becomes a clear winner, create 100 k-exchange arrays of size 10,000,000, run in turn the chosen sorting methods on each array, and collect running times. Based on the collected running times, draw your conclusion with justification. Is your conclusion consistent with the conclusion of www.sorting-algorithms.com?
Please submit your the modified code, including your conclusions and a transcript of its execution, in the ICON dropbox for Project2 before the deadline.