- To apply your understanding of sorting algorithms by writing your own Java program
- To extend your knowledge of sorting algorithms by writing a hybrid algorithm
- To demonstrate your knowledge of order statistics by performing an analysis of the hybrid algorithm
Requirement 1: Sorting Algorithms - General purpose implementation.
- Implement selection sort, bubble sort, insertion sort, merge sort and quicksort in a single Java class (SortingAlgorithms.java), measure and output the (“wall clock”) time required for each algorithm to sort the array
- Your implementation must contain a function with a signature as follows: long sort(String algorithm, float [] arr), where valid values for “algorithm” are one of: “selection”, “bubble”, “insertion”, “merge” or “quick”. The return value will be the time required to sort the array in milliseconds
Requirement 2: Graph of times.
- Generate an array of randomly-generated values of varying lengths. The array lengths must be minimally every 50,000 up to 500,000... in other words: 50,000, 100,000, 150,000, ..., 500,000. Execute the algorithms above (selection sort, bubble sort, insertion sort, merge sort and quicksort) against a copy of the array. Keep track of the algorithm, the running times and the algorithm execution time.
- Using an external tool — eg. Google Sheets, OpenOffice Calc or Excel — produce a chart of the algorithm, the running times and the algorithm execution time. This chart must look like Figure 1, with additional data for merge sort and quicksort included.
Requirement 3: Quicker than quicksort?
- Implementat a new algorithm that will combine randomised quicksort with the quadratic sort of your choosing to make a faster hybrid sort. In an implementation of randomised quicksort, the algorithm selects a random element of the (sub-)array as a pivot. Your algorithm will run quicksort until the subarray size becomes small enough, the point at which quicksort likely becomes inefficient. On the “small-enough” subarray, your implementation will run the quadratic sort until the subarray is sorted
- Implement this hybrid sort in a single Java class (QuickerThanQuicksort.java).
- You must choose the following: Which quadratic sort will you use to sort the “small enough” subarray? What is the minimum number of elements in a subarray for quicksort? (Alternatively: what is the maximum size of a subarray to be sorted by the quadratic sort?)
- While the quicksort algorithm normally does not return a value (i.e. it is a void function), your implementation will likely require the index of the pivot value so that it may be integrated with the rest of your implementation.
- If the input to quicksort is the following 8-item array: [ 5, 2, 9, 12, 6, 8, 3, 7 ], the algorithm begins by randomly selecting one of these items to be the pivot. Assuming the value 6 (at index 4) is selected as the pivot, the quicksort algorithm proceeds as we discussed. The resulting array may be as follows: [ 5, 2, 3, 6, 7, 8, 9, 12 ]. The algorithm returns the value 3 (the index of the pivot after the partition algorithm has been executed), indicating that the left subarray is [ 5, 2, 3 ] and the right subarray is [ 7, 8, 9, 12 ].