This assignment is extra credit! You will satisfactorily demo your assignment to the professor in person before 4PM on May 11, then submit your files on Blackboard. Grading will be binary on each part of the assignment – you will either have a working solution which you can adequately explain and which uses good practices in which case you will get full credit, or you will get no credit. You may demo once per day up to the deadline in an effort to get credit for the assignment.
Part 1 (50%): Have a completely working game! Your game must work to the specifications provided in the project description and assignments 1-6, and you must be able to explain your code and choices you’ve made.
Part 2 (50%): Implement quicksort for arrays of ints. We will discuss this algorithm in class before the final day of the semester. You will need to implement three methods, with the following signatures:
|
1 2 3 |
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 (1) random data, (2) sorted data, and (3) 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.