Quick Sort Comparison

Project Specification

Consider the two algorithm optimization proposals QuickSortOpt1 and QuickSortOpt2, described below. QuickSortOpt1 executes QuickSort until partitions size gets lower than a given cutoff value (usually set to 10) and then, executes InsertSort for sorting the small partitions.

QuickSortOpt2 executes QuickSort until partitions size gets lower than a given cutoff value (usually set to 10) and then, executes InsertSort on the whole almost sorted array.

Design and implement a Java program which defines an array of size SIZE, randomly populated with Integer or int values in the range 1 .. MAXRNG and sorts the array in increasing order of its values using QuickSort (the original), QuickSortOpt1 and also by QuickSortOpt2.

Consider two program execution cases defined by the value of the boolean constant SHOW.

a) (SHOW value is true). The program should display the array values before sorting and then after invoking each sorting method. For this case, consider SIZE value 100 and MAXRNG value 9999.

b) (SHOW value is false). Measure the execution time of the three sorting algorithms using System.nanoTime() method and display their average values for 10 runs (array values should not be shown). Fill-in the table below with the measured values considering SIZE value 100,000 and MAXRNG value 999,999. Discuss the obtained results (how do the two proposed QuickSort variations compare with the original and with each other?).

Algorithm Measured mean values of the execution time

QuickSort
QuickSortOpt1
QuickSortOpt2

HINTS

1) For the original QuickSort algorithm, see the online materials; use that code as a reference for Quicksort implementation in Java.

2) Run your three algorithms first with the SHOW variable set to true until you see that everything works correctly. Then switch to false and perform the time measurements.

3) Clearly QuickSortOpt2 will not be applied on the data resulting from QuickSortOpt1, because that data is already sorted; all three algorithms will be applied on the same data, otherwise the comparison does not make any sense.