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.

1. Complete this implementation by defining the generic BucketList class, which represents a bucket list (i.e., list of lists). At a minimum, your class should provide the following functionality: public class BucketList<E> { // private fields not shown /** Constructs a list of empty buckets * @param size the number of buckets (size > 0) */ public BucketList(int size) { . . . } /** Adds an item to the specified bucket * @param bucketNumber the number of the bucket (bucketNumber >= 0) * @param item the item to be added * @return whether the add was successful */ public boolean add(int bucketNumber, E item) { . . . } /** Accessor for bucket list size * @return the number of buckets in the list */ public int size() { . . . } /** Accessor for the number of items * @return the number of items stored in the entire list */ public int numStored() { . . . } /** Accessor for a particular bucket * @param bucketNum the number of the bucket (bucketNumber >= 0) * @return a list containing the items in that bucket */ public ArrayList<E> getBucket(int bucketNum) { . . . } /** Converts the bucket list to a single ArrayList of items * @return an ArrayListlist containing all items in the list, preserving order */ public ArrayList<E> asList() { . . . } /** Removes all items, leaving a list of empty buckets */ public void clear() { . . . } }

   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 BucketLists and test the methods on those lists.
   
   

2. Once you have your 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.
   
   

3. Once you have your 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.