CSC 321: Data Structures
Fall 2016

HW3: Radix Sort & Efficiency

For this assignment, you will complete the radix sort implementation discussed in the lecture and perform timing experiments on the sort. The basic code for radix sort is provided in

  1. Complete this implementation by defining the generic BucketList class, which represents a bucket list (i.e., list of lists). The functionality of your class is described in the BucketList javadoc.

    Note: you should test your BucketList class thoroughly before proceeding with the rest of the assignment.

  2. Once you have your BucketList class tested, you can test the static radixSort method in the Radix class. As it is currently written, this sort assumes that all words in the list have the same length (determined by the constant STR_LENGTH). Modify the code so that the sort works for words of varying lengths. Your modification must not change the overall big-Oh efficiency of the algorithm. That is, the radix sort implementation should be O(maxStringLength * N), where N is the number of words.

    Note: you should test your modified radixSort method thoroughly before proceeding with the rest of the assignment.

  3. Once you have your radixSort code tested, write a Driver class named RadixDriver that times the execution of the radixSort method on lists of increasing sizes. You may utilize the StopWatch class, which provides a simple (and simplistic) way of measuring execution time. Note that the elapsed time reported by this class is clock time, which is affected by many factors other than code execution (e.g., background jobs, garbage collection). To try to minimize these factors when using a StopWatch, you will want to limit background jobs and also perform multiple timings to identify and disregard outliers.

    The data files words20K.txt, words40K.txt, words80K.txt, words160K.txt, words320K.txt, and words640K.txt have been provided, which contain 20 thousand, 40 thousand, 80 thousand, 160 thousand, 320 thousand, and 640 thousand randomly shuffled words, respectively. Does your implementation exhibit O(maxStringLength * N) performance? Show your timings and explain your answer.

  4. How do your radix sort timings (and associated rate of growth) compare with the implementation of quick sort found in Collections.sort? Show your timings and explain your answers.

You should turn in a single ZIP file containing your BucketList class, your modified Radix class, and the RadixDriver class you wrote to perform timings. In addition, you should turn in the timings and written explanations from part 3.