Reference no: EM131598080

She has a large file of students she would like to sort. It would be helpful to her to have the students sorted by the school they are attending and students attending the same school sorted by ID in ascending order. For example:
Joe Paarmann, 3, UCB
Otha Baloy, 5, UCB
...
Alton Hamblet,1,UCD
Jessie Merle,7,UCD
Lawanda Doell,9,UCD
...
Alva Zajicek, 4, UCI
...
Chester Kemfort,2,UCLA
Alice Mines,6,UCLA
...
She tried sorting the students herself but when she sorts by school the students are no longer sorted by ID within each school, and vice-versa. Having learned of stable sorting you agree to take on this simple task.

Part 1:
You plan to use the Java library stable sort to do the sorting. Since the sort is stable, you can do two consecutive sorts and end up with the needed result (note that which sort you do first matters).

To sort a list by some criteria in Java 7, you use the Collections.sort() method like below. The second argument is an implementation of the Comparator interface, which determines how two elements are compared.
Collections.sort(myList, myComparator);

Part 2:
It occurs to you that you don't need two separate sorts. You plan to write a single comparator that sorts by school and breaks ties by ID and use that to sort only once to get the desired result.

Part 3:
Both parts 1 and 2 were simple and fast enough, but you have a hunch you could probably make this a tiny bit faster. You decide to implement your own simple algorithm for the problem based on bucket sort. The idea is very simple:

- You create one bucket (a list) for each school.
- You do one pass through the input list and place each student you encounter into its corresponding bucket.
- You sort each of the buckets (by which field?) by using a comparator like in Part 1.
- You go through each bucket in order and put the students one by one into the original list.Hints:

A lot of the code has been given. All you need to do is fill out the empty bodied methods.

Make sure you are comfortable using the ArrayList class(we have seen most methods you will use in the lists lecture) and doing a simple sort using a comparator. You may want to try that with a list of strings first, just for some quick practice.