Design and implement an algorithm that finds all the duplicates
in a random sequence of keys.
Suppose we wish to sort a sequence of data represented using
the linked-list class LinkedList
introduced in Program .
Which of the sorting algorithms described in this chapter
is the most appropriate for sorting a linked list?
Design and implement a linked list sorter class
that implements this algorithm.
Replace the Sort method of the MergeSorter class
with a non-recursive version.
What is the running time of the non-recursive merge sort?
Replace the Sort method
of the AbstractQuickSorter class
with a non-recursive version.
What is the running time of the non-recursive quick sort?
Hint: Use a stack.
Design and implement a radix-sorter class that sorts
an array of strings.
Design and implement a RandomPivotQuickSorter class
that uses a random number generator (see Section )
to select a pseudorandom pivot.
Run a sequence of experiments to compare the running times
of random pivot selection with median-of-three pivot selection.
Design and implement a MeanPivotQuickSorter class
that partitions the sequence to be sorted
into elements that are less than the mean
and elements that are greater than the mean.
Run a sequence of experiments to compare the running times
of the mean pivot quick sorter with median-of-three pivot selection.
Design and implement a MedianPivotQuickSorter class
that uses the algorithm given in Exercise
to select the median element for the pivot.
Run a sequence of experiments to compare the running times
of median pivot selection with median-of-three pivot selection.
Design and implement a sorter class
that sorts using a PriorityQueue instance.
(See Chapter ).