Assignment #6: Quicksort with Heapsort and an STL Interface
This assignment requires that you implement quicksort so that if any recursive
call is too deep, a call to heapsort is automatically made.
The interface will mirror the STL.
Spec
You will implement the following routines (all are templates,
but the template declarations are not shown):
void quicksort( Iterator begin, Iterator end );
void quicksort( Iterator begin, Iterator end, Comparator lessThan );
void quicksort( Iterator begin, Iterator end, Comparator lessThan, int depth );
void heapsort( Iterator begin, Iterator end, Comparator lessThan );
Remember that this means that all elements in the range starting from
begin and ending at the element prior to end
are to be sorted.
Algorithm
The two parameter quicksort is
logically implemented by calling the three parameter quicksort
with the third parameter equal to the comparator less<Object>.
The three parameter quicksort is logically implemented by calling the four
parameter quicksort with the fourth parameter equal to 2logN.
(You will need to determine N, and compute the logarithm to the base 2.)
The four parameter quicksort uses the logic in the text to implement
median-of-three quicksort, with a cutoff of 10 for switching to
insertion sort.
However, prior to testing for the insertion sort cutoff, test depth.
If depth is zero, call heapsort and return.
Otherwise, continue as before; however, the recursive calls to
quicksort should use depth-1.
(In effect, if any recursive call is too deep, the recursion is abandoned and
heapsort is used for that subproblem.)
In median-of-three quicksort, you need to, in effect, compute the
average of two iterators.
You cannot add two iterators, but given to iterators
a and b, the average of a and b,
which is logically (a+b)/2 can be computed as
a+(b-a)/2.
Note that in writing heapsort you will need slight changes
to the text algorithm because there will not be a sentinel.
In effect, the element in position begin will correspond
the position 0, and so redo the left and right child calculations
to work when the root is at position 0 instead of position 1.
STL Implementation Details
There are substantial complications.
Look at insertsort.cpp to
see how this works for insertion sort.
You will need to write extra template routines.
The two and three parameter quicksort must follow the protocol
shown above.
The four parameter quicksort and the heapsorts are helpers and
you can change the interfaces if you think of a better way.
Specifically, you can use different names, and heapsort
can have additional parameters as you see fit.
But you must use the basic algorithm of switching to heapsort
if the depth gets too deep.
Also note that there is already a swap routine in the
STL.
If it works for you, you can use it; if not, you will need
to write your own (probably using a different name to avoid conflicts).
Test Program
Maintain a (global, or equivalent) variable that counts how many times
heapsort is called.
Test your code on 50 instances of random 10,000 item sequences, as well
as the sorted and reverse-sorted sequence,
and a sequence consisting of 10,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.
Also test your code on 50 instances of random 10,000 item sequences,
but call the four parameter quicksort directly, using 1.5logN.
This should generate calls to heapsort.
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 Tuesday, December 5.