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 Sorts.java.
BucketList
class,
which represents a bucket list (i.e., list of lists). At a minimum, your class should provide
the following functionality:
Note: you should test your BucketList
class thoroughly before proceeding
with the rest of the assignment. You should write a Main
class which
constructs various BucketList
s and test the methods on those lists.
BucketList
class tested, you can test the
static radixSort
method in the Sorts
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 Main
class
that times the execution of the radixSort
method on lists of various sizes.
The data files words10K.txt, words20K.txt,
words40K.txt, words80K.txt have been provided,
which contain 10 thousand, 20 thousand, 40 thousand, and 8 thousand randomly
shuffled words, respectively. Does your implementation exhibit O(maxStringLength * N)
performance?
Show your timings and explain your answer. How do these timings (and associated rate of growth)
compare with the selectionSort
method that is also part of the Sorts
class? How do they compare with the Collections.sort
method that is part of the
Java libraries? Show your timings and explain your answers.
You should turn in (via the Digital Dropbox) a NetBeans project containing your
BucketList
class, your modified Sorts
class, and the
Main
class you used to perform timings. In addition, you should turn in the
timings and written explanations from part 3.