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 Radix.java.
BucketListclass, 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.
BucketListclass tested, you can test the static
radixSortmethod in the
Radixclass. 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.
radixSortcode tested, write a Driver class named
RadixDriverthat times the execution of the
radixSortmethod 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.
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.