Problem: The goal of this assignment is to empirically evaluate Quicksort with two different variations: (JAVA Program Preferably)
Use of a randomized pivot - index randomly chosen between positions low and high - compared to using a fixed pivot such as position low or high.
Switching to Insertion Sort for small sub-arrays, i. e. when high - low < threshold
To empirically measure the performance of Quicksort, you should track both:
The clock time taken by the algorithm (subtract clock time at start from clock time at end)
The number of comparison operations performed (use a global variable ncomp for number of comparisons, and increment it each time you do a comparison)
Run Quicksort for a variety of sizes (say n = 10, 100, 1000, 10000), for several trials of random data for each n, and track both the number of comparisons and clock time for each trial.
Assuming that the switch to Insertion Sort for smaller sizes improves performance, run additional trials to determine the optimal threshold, the point at which the algorithm switches from Quicksort to Insertion Sort.
Document all this in appropriate tables that clearly show the comparisons and clock-times for the various runs of your algorithm. Let the algorithm do the work and build the tables for you. (For Python users, Tabulate and Tabletext are two libraries that can help you achieve professional looking tables that document your effort and results.) You can also write results to a file if you cannot run them all at once.
(Instruction: It does not have to be a proper table, but should reflect the comparisons in a clear manner in the console output. General threshold for switching to Insersion Sort is about array size less than or equal to 10)