Assignment 7 is extra credit!
In this assignment you will implement and examine the properties of the quicksort algorithm. Specifically, you will:
- Implement quicksort for arrays of ints. You may want to use the mergesort code from class as a template. You will need to implement three methods, with the following signatures:
- private int partition(int arr[], int first, int last)
- private void quickSort(int arr[], int first, int last)
- public void sort(int arr[]) – This method just calls quickSort.
- Implement benchmarking routines examining the performance of quicksort on different size inputs for
- Random data
- Sorted data
- Reverse sorted data
- In a comment at the end of your program file, include the timing results for these three benchmarks on 10 different size inputs, starting at 40,000 and doubling the size each time.
- In a comment at the end of your program file, consider how you might improve quickSort to perform roughly equivalently on all orderings of input. Consider exotic input arrangements which could break your optimizations.
- Copy your code to another file and implement your changes there. Repeat your benchmarks. Discuss whether you were successful in a comment.