### CSC 427: Data Structures and Algorithm Analysis Fall 2006 HW2: Radix Sort & Efficiency

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 `BucketList`s 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.