15-121 Homework 5: Implementing Radix Sort - Due 11/12 at midnight

Download and unzip hw5-code.zip, which contains all the files you will need for this assignment. You will be writing code in a number of files, as well as creating a new class file that implements a Comparator. The goals of this assignment are:

to put you on the client side for a little bit
to familiarize you with radix sort
to gain more experience with implementing interfaces
to use the list (as a queue) that you wrote in the last assignment

Note: You will be graded in part on your coding style. Your code should be easy to read, well organized, and concise. You should avoid duplicate code.

Background: The Assignment

You're going to modify the Student and Roster classes that we used back in the lecture on Iterators. In particular, you're going to have the Student class implement Comparable<Student> so it can be sorted (using Collections.sort()), you're going to write a class that implements Comparator<Student> so that you can compare Students in a different manner than the way compareTo() will, you're going to use the MyList class that you wrote for HW4 to implement the queues that are necessary for radix sort, and you're going to implement radix sort!

Process

The first thing you should look at is the HW5Driver.java file. This is the test driver for the program (pretty short, isn't it?). The first part creates a test course that you can use to make sure things are working. The second part invokes the same methods on a roster that is built from the data for our current course.

As you can see, there are some new methods that you're going to have to write for the Roster class. They include:

void sortStudents() - sorts the students according to the order prescribed by compareTo in the Student class. Of course, the Student class doesn't currently implement the Comparable interface, so you're going to have to fix that (by having Student implement Comparable<Student>). It should do this, by the way, in the "normal" way, by comparing last names and, if they are equal, first names. Once Student implements Comparable<Student>, you do not have to write a sort for this method; just call Collections.sort(). Ahh, the power of the Java Collections Framework! By the way, don't forget that once you implement compareTo, you should override equals in a manner that is consistent with compareTo returning 0.
void sortByIDComparator() - a drawback to Comparable is that it limits you to only one way of comparing. Suppose we want to sort our students by andrewID (and we do!). compareTo() is of no use! Ahh, but fear not. You can create (and you will) a class (called whatever you want) that implements Comparator<Student>, that has one method: compare(Student, Student), that will compare students correctly by andrewID (andrewID's that are alphabetically less should come before those that are greater, the standard ordering for Strings). Once the Comparator class is built, this method is two lines to write. One to construct an instance of the Comparator, and one to call (and pass that instance to) Collections.sort().
Roster(String courseSection, String fileName) - an additional constructor for the Roster class that takes two parameters, the second of which is the name of a file to read from and build the roster. You should probably look at the file I/O code from Lecture 6 to refresh your memory about how to open and read from a file of Strings. The file, if it exists, is guaranteed to have three Strings per line: first-name, last-name, andrew-id. The constructor should open the file, handle exceptions appropriately (including if the file is not found), and build the ArrayList of students from the data in the file. Feel free to write/use any helper methods you need.
void sortByID() - here's the meat of the assignment. You are going to implement a radix sort that sorts the students in the list by their andrewID. Since this is a string, you will need 26 buckets (well, 27 really, since you need a place to put the id's that don't have a character in the position you're currently sorting on. You will absolutely need helper methods here, as will be discussed below.

Radix sort

As you should recall from lecture, radix sort works on integers, but we can extend that to Strings. As the lecture demo noted, we start with the least significant value first (this would be the right-most character in the andrewID). Since we're dealing with characters, we'll need 26 buckets plus one for strings that don't have a letter in the position that we're examining. So you'll need a method to extract individual characters from andrewID's. Also, each of the 27 buckets will need to hold a queue of students since, as noted in lecture, every time you insert a value that you're sorting, it goes at the end of the ones already in that bucket.

Unfortunately, Java does not like generic arrays, so you'll need to either declare your collection of buckets as

    MyList[] myQueues = new MyList[27];

and deal with casting all the time (UGH!), or declare your collection as

    ArrayList<MyList<Student>> myQueues = new ArrayList<MyList<Student>>();

but have to access using the get(index) method. As for me and my house, I'm going with the ArrayList. Don't forget that when you declare and construct an ArrayList of objects, there's nothing there until you add/construct them (i.e., it's an ArrayList of nulls!).

For each position in an andrewID, you will have to go through all the students on the roster and put them in the correct queue based on the character (or none) at that position in their id. You'll have to deal with Strings of different length, since andrewIDs are not all the same length and recall that an andrewID like mjs will have m in the 0th position, j in the 1st position, and s in the 2nd position. Consider where the most significant character is and what you need to do with andrewID's that have less than 8 characters. I smell a helper method...

After you have all the students in the correct queues, you'll need to gather them all up and put them back in the original ArrayList and do it again for the remaining character positions. When you've done this 8 times (the maximum number of characters in an andrewID, they should all be sorted. And you're done.

HINT: I would do the sortByID() method last.

Submitting Your Work

When you have completed the assignment and tested your code thoroughly, create a .zip file with your work (including Student.java, Roster.java, the Comparator class and any other files that you modified. Name the zip file "your-andrew-id".zip and email it to me mjs @ cs.cmu.edu.

Make sure to keep a copy of your work just in case!