Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Projects

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 ).