Assignment #3: Quicksort with Mergesort and an STL Interface
This assignment requires that you implement quicksort so that if any recursive
call is too deep, a call to mergesort 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 mergesort( 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 mergesort 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
mergesort is used for that subproblem.)
Note: you cannot add two iterators and divide by 2 to get a midpoint.
However, you can get the midpoint of itr1 and itr2
as itr1 + (itr2-itr1)/2.
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 mergesorts are helpers and
you can change the interfaces if you think of a better way.
Specifically, you can use different names.
But you must use the basic algorithm of switching to mergesort
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
mergesort 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
mergesort 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 mergesort.
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 Thursday, Oct 14.