Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Projects

  1. Design and implement an algorithm that finds all the duplicates in a random sequence of keys.
  2. Suppose that instead of an Array<T> instance, we wish to sort a sequence of data represented using the linked-list 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.
  3. Replace the DoSort routine of the MergeSorter class with a non-recursive version. What is the running time of the non-recursive merge sort?
  4. Replace the DoSort routine of the QuickSorter class with a non-recursive version. What is the running time of the non-recursive quick sort? Hint: Use a stack.
  5. Design and implement a radix-sorter class that sorts an array of string class instances.
  6. Design and implement a RandomPivotQuickSorter class that uses a random number generator (see Section gif) 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.
  7. 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.
  8. Design and implement a MedianPivotQuickSorter class that uses the algorithm given in Exercise gif 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.
  9. Design and implement a sorter class that sorts using a PriorityQueue instance. (See Chapter gif).


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.