Your cart is currently empty!
These must be completed and shown to your lab TA either by the end of this lab, or at the start of your next lab. You may work in groups of up to two people. Download qsortCount.cpp from the course web page. The remaining questions are about how to instrument Quicksort in order…
These must be completed and shown to your lab TA either by the end of this lab, or at the start of your next lab. You may work in groups of up to two people.
The remaining questions are about how to instrument Quicksort in order to evaluate its average case performance empirically and then to simplify the instrumented code until the recurrence for the average case performance is revealed.
Run your program using array size 1000 for 100 repetitions. What is the average number of compar-isons?
Run your program with a few di erent choices of NN (array size). How does the number of comparisons change with NN?
Note: Write code in main to do this experiment.
Write a new recursive function qc that takes a single parameter n and returns the number of compar-isons quicksort would perform in sorting an array of size n, but doesn’t sort anything. (You’ll call randint to pick a random pivot location.)
float c(int n) {
if (n <= 1) return 0; float sum = 0.0;
for (int m=1; m <= n; m++) sum += n-1 + c(m-1) + c(n-m);
return sum / n;
}
Write the value, C(n), returned by c(n) as a recurrence relation. (It will have a summation and should look similar to the program, but in mathematical notation.)
Warning: You should not run this code for n much bigger than 20 unless you’re very patient (and have a long life). The running time is (3n).
What are the run times for quicksort in A) the average case, and B) the worst case? Why are you unlikely to observe the worst-case run time, in practice?
Is our implementation of quicksort an in-place sort? Is it a stable sort? Why or why not?
You could implement this either recursively, storing the results of recursive calls so that each call is never made twice (memoization), or you could do it iteratively, with a nested for-loop. When you complete the iterative version, you can try going even further by removing the inner for-loop.
(see also the next page)
1
CPSC 221: | Lab 6 |
8. (Optional, not for nmarks) Solve the recurrence for C(n) to show that C(n) 2 (n log n). | It will |
P
help to know that i=1 1=i is (log n).
2