Notes: Of the three problems given below, one will be solved by the TAs in next week's discussion section, you will have to solve one in class, and the remaining problem is due in the lecture on Friday, 4/14.
For each value of n generate an array of size n called randomList, with integers in the range 1 through n, chosen randomly. It is okay for this array to contain duplicates. Run quick sort and randomized quick sort on randomList and record the running times of these functions. Then take the sorted version of randomList, reverse it, and create another array of elements, called reverseList. Run quick sort and randomized quick sort on reverseList and record the running times of these functions. Repeat this 10 times (for the same value of n) and compute average running times. You should have 4 average running times: (i) quick sort on randomList, (ii) randomized quick sort on randomList, (iii) quick sort on reverseList, and (iv) randomized quick sort on reverseList.
Finally, repeat this for values of n equal to 10000, 11000, 12000, ..., 19000. Produce 4 plots, each with n on the x-axis and average running time on the y-axis. Comment on your plots, indicating whether they correspond to theoretical predictions. (1) Use partition with no trick. Generate (a) random input and (b) input sorted in reverse order. Run quick sort, time, and explain results. (2) Use partition with randomization. Generate (a) random input and (b) input sorted in reverse order. Run quick sort, time, and explain results.