Please help with this program in Java. Quickersort - optimized version of Quicks
ID: 3696083 • Letter: P
Question
Please help with this program in Java.
Quickersort - optimized version of Quicksort Implement an optimized version quicksort algorithm with the following changes: Pivot: First element (or any random element) and median of a [left], a [center], and a [right] of the subarray (or any three random elements in the subarray) Cutoff to insertion sort for subarrays with less than M elements from 0 to 30. You need to add the following two methods: getPivot(a, lo, hi) method that returns the pivot element based on your chosen strategy in the subarray a[lo..hi] insertionSort(a, lo, hi) that sorts the subarray a[lo..hi] Empirically determine the value M for which value of quicksort runs fasted in your environment to sort random arrays of N doubles, for N 10^3, 10^4, 10^5, and 10^6. Plot the average running times for M from 0 to 30.Explanation / Answer
a)The important thing in quicksort is to select a pivot element.
the main reason of why a perfect pivot should be selected because if the pivot is not selected accordingly then worst case of O(n^2) will come.Always choosing first or last would cause worst-case performance for nearly-sorted or nearly-reverse-sorted data.
Never choose a fixed pivot element everytime.
In normal quicksort the first element is automatically the pivot item. This causes normal quicksort to function very inefficiently when presented with an already sorted list.
Using median of three elements:
median-of-three' (first, last, middle) is also a way of avoiding problems. Beware of relative performance of comparisons, though; if your comparisons are costly, then Median of three does more comparisons than choosing (a single pivot value) at random. Database records can be costly to compare.
b) This moddification will definetely likely to speedup sorting. Insertion sort works better for small subarrays. Insertion sort can be used for invocations on such small arrays.
1) Partition process is same in both recursive and iterative. The same techniques to choose optimal pivot can also be applied to iterative version.
2) To reduce the stack size, first push the indexes of smaller half.
3) Use insertion sort when the size reduces below a experimentally calculated threshold.
Insertion sort is faster than quicksort for smaller sets so therefore we divide the larger sets into smaller sets and perform insertion sorts on them. Therefore it decreases the time taken for performing optimized quick sort.