Assignment #6: Quicksort with Heapsort
This assignment requires that you implement quicksort so that if any recursive
call is too deep, a call to heapsort is automatically made. The basic ideas
are described in the end-of-chapter exercises in Chapter 7.
Steps
-
Do Exercise 7.14.
-
As suggested in Exercise 7.27, change the recursive quicksort by adding
a parameter depth, from the driver that is approximately 2 log
N.
-
If the subarray size is less than 10, call insertion sort to
sort the subarray.
-
Otherwise, if depth is zero, call heapsort to sort the subarray.
-
Otherwise, perform the normal quicksort, passing depth-1 to the
two recursive calls.
-
Maintain a (global, or equivalent) variable that counts how many times
heapsort is called.
-
Test your code on 50 instances of random 100,000 item sequences, as well
as the sorted and reverse-sorted sequence,
and a sequence consisting of 100,000 zeros.
Verify that the sorts work (make
sure that the items are not only non-decreasing, but that they are the
same as what you started with), and provide statistics on how often the
heapsort is called on the random and non-random inputs.
What To Submit
Submit all your source code. Explain your testing methodology. Provide
statistics in a nice tabular format, with an explanation.
Due Date
This program is due on Monday, August 9.