Description
In this lab, you will implement a base case improvement for quicksort. Your TA will overview these sor ng algorithms and the op miza on.
Exercise
-
er the TA’s lesson, complete the following steps:
-
-
Download the provided code and read it over.
-
-
-
Run SortTiming to determine the size at which inser on sort becomes less efficient than quicksort. Recommended parameters are 1000 trials, ranging from size 5 to 100 with step size 1.
-
Hint: Use output redirec on to save the output of this program to a text file with a csv extension. This text file can then be opened in a spreadsheet program, such as Excel, enabling you to plot graphs for your results. Use a command such as:
java cs445.lab11.SortTiming > data.csv
-
Implement the method timeQuickSort2() based on timeQuickSort . For the sort itself, you should use the quicksort wrapper that allows you to specify the base case size, and then call inser on sort to “smooth out” the resul ng array. Use a base case for which inser on sort is clearly faster than quicksort.
-
Uncomment the call to timeQuickSort2() in main() , and re-run the experiment for a larger range of sizes. Compare the run me of quicksort vs. your improved version of quicksort. Suggested parameters are 1000 trials, ranging from size 10 to 1500 with step size 10. Draw a plot of these results to evaluate your op miza on.
In this lab, you wrote an op miza on for quicksort, increasing the base case size and using inser on sort for the smallest subarrays. While this is not an asympto c improvement, it can be a significant prac cal movement.
