Data Structures and Algorithms
with ObjectOriented Design Patterns in C++

Design and implement an algorithm that finds all the duplicates
in a random sequence of keys.

Suppose that instead of an Array<T> instance,
we wish to sort a sequence of data represented using
the linkedlist class LinkedList<T>.
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 DoSort routine of the MergeSorter class
with a nonrecursive version.
What is the running time of the nonrecursive merge sort?

Replace the DoSort routine of the QuickSorter class
with a nonrecursive version.
What is the running time of the nonrecursive quick sort?
Hint: Use a stack.

Design and implement a radixsorter class that sorts
an array of string class instances.

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 medianofthree 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 medianofthree 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 medianofthree pivot selection.

Design and implement a sorter class
that sorts using a PriorityQueue instance.
(See Chapter ).
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.