CSC 427: Data Structures and Algorithm Analysis
Fall 2007

HW2: Radix Sort & Efficiency


For this assignment, you will complete a radix sort implementation 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 ListOfBuckets class, that is used by the radixSort method. The functionality of your class is described by the ListOfBuckets.html javadoc page. Be sure to design your class to meet these specifications exactly, or else the radixSort method will not work correctly.

    Note: you should test your ListOfBuckets class thoroughly before proceeding with the rest of the assignment. You should write a Main class which constructs various ListOfBuckets objects and tests the methods on them.

  2. Once you have your BucketList class tested, you can test the provided radixSort method. Write a Main class that times the execution of the radixSort method on lists of various sizes. The data file words5.txt contains all 8,551 5-letter words in the online dictionary, randomly ordered. The files double5.txt and quadruple5.txt contain those words repeated two and four times, respectively. Does your implementation exhibit O(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? Show your timings and explain your answers.

You should turn in (via the Digital Dropbox) a NetBeans project containing your BucketList class, the provided Sorts class, and the Main class you used to perform timings. In addition, you should turn in the timings and written explanations from part 2.