Data Structures and Algorithms
with Object-Oriented Design Patterns in Java
-
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 ).
Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.