Implement the following improvement to the quick sort and find out the percentage of key comparisons that can be saved in each case. Using randomly generated 1000 integers as input for sorting. Repeat the experiment 1000 times for each case to get the average percentage reduction in key comparisons.
Case 1. Median of Three Partition
Case 2. Sort partition of size less than 16 directly using Insertion sort
Case 3. Combine both techniques above.
Please let me know how do I do this?
Thanks in advance.