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.
BucketListclass, 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
BucketLists and test the methods on those lists.
BucketListclass tested, you can test the static
radixSortmethod in the
Sortsclass. 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
Mainclass that times the execution of the
radixSortmethod 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
selectionSortmethod that is also part of the
Sortsclass? How do they compare with the
Collections.sortmethod 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.