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