Implement two algorithm optimization proposals QuickSortOpt1 and QuickSortOpt2, explained below. QuickSortOpt1 executes QuickSort until partitions size gets lower than given cutoff value (usually 10) and then, executes Insertion Sort for sorting small partitions. QuickSortOpt2 executes QuickSort until all partitions size gets lower than given cutoff value (usually 10) and then, executes improved Bubble Sort algorithm upon whole "almost sorted" array.
Part 1
Design and implement the QuickSortOpt1 and QuickSortOpt2 algorithms. Write a Java program to test the functionality of these algorithms. Define an array of size 100, randomly populated with Integer or int values in the range 1 .. 999 and sort the array in increasing order by using the QuickSort algorithm followed by QuickSortOpt1 and then by QuickSortOpt2. Display the array content before sorting and then after invoking each sorting method.
Part 2
Using System.nanoTime() method, measure execution time of three sorting algorithms, for each of the array sizes, and display average execution time values for 10 runs. Consider the arrays as being randomly populated with Integer or int values in the range 1... MAX.
The algorithms must be executed and the required values should be displayed within one run, without modifying the source code and recompiling the project file(s).
a) All .java source files.
b) Screenshots showing program execution and results of your testing.
c) A document file relating your solution. The solution explanation document must include the following elements: a short problem analysis, major design decisions, suppositions, explanation of classes, user interface, testing and test cases, error handling, results and lessons learned. In the results section, fill-in the Part1 Part 2
Deliverables
Measure values by considering indicated array size SIZE and the corresponding random array values in the range 1 ...MAX. Describing the results. The size of the document must be of 3 pages, single spaced, font size 12. All solution explanation elements must be properly formatted using APA style.