Satisfied with the work you did finding SMC alumni at UC schools, your boss has
ID: 3836661 • Letter: S
Question
Satisfied with the work you did finding SMC alumni at UC schools, your boss has come to ask for your help again. 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. API docs are here: http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html // do not implement equals() method
public class Project4 {
/**
* Read students from file into a list
*
* @param filename
* @return the list of students
*/
static ArrayList<Student> readFromFile(String filename) {
ArrayList<Student> students = new ArrayList<Student>();
try (Scanner in = new Scanner(new File(filename))) {
while (in.hasNextLine()) {
String[] fields = in.nextLine().split(",");
students.add(new Student(Integer.parseInt(fields[1]), fields[0], fields[2]));
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
return students;
}
/**
* Write the students to a file
*
* @param students
* @param filename
*/
static void writeToFile(ArrayList<Student> students, String filename) {
try (FileWriter out = new FileWriter(filename)) {
for (Student s : students) {
out.write(s.toString());
out.write(" ");
}
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* Sorts the students list by school. Same school students are sorted by ID.
*
* Performs two stable sorts with different criteria. One sort and then another sort.
*
* @param students
*/
static void sortBySchoolById1(ArrayList<Student> students) {
// Your code here
}
/**
* Sorts the students list by school. Same school students are sorted by ID.
*
* Performs only one sort that uses a comparator that takes both criteria
* into account.
*
* @param students
*/
static void sortBySchoolById2(ArrayList<Student> students) {
// Your code here
}
/**
* Use this function in your bucket sort
*
* Return the bucket index for each school (schools in alphabetical order)
*
* "UCB", "UCD", "UCI", "UCLA", "UCM", "UCSD", "UCSF"
* 0 1 2 3 4 5 6
*
* @param school
* @return the bucket index
*/
private static int schoolToIndex(String school) {
switch (school) {
case "UCB":
return 0;
case "UCD":
return 1;
case "UCI":
return 2;
case "UCLA":
return 3;
case "UCM":
return 4;
case "UCSD":
return 5;
case "UCSF":
return 6;
default:
System.err.println("Unknown school " + school);
return -1;
}
}
/**
* Sorts the students list by school. Same school students are sorted by ID.
*
* Places all the students of the same school into an individual bucket and
* sorts each bucket separately.
*
* @param students
*
*/
static void sortBySchoolById3(ArrayList<Student> students) {
final int NUM_SCHOOLS = 7;
// an array of lists. Each element is a reference to a list.
ArrayList<Student>[] buckets = (ArrayList<Student>[]) new ArrayList[NUM_SCHOOLS];
// Your code here
}
public static void main(String[] args) {
ArrayList<Student> students1 = readFromFile("students.txt");
// make 2 other copies so we don't have to read the file again
ArrayList<Student> students2 = new ArrayList<Student>(students1);
ArrayList<Student> students3 = new ArrayList<Student>(students1);
// let's time the three sorts for fun. Not really that accurate.
long start, end;
start = System.currentTimeMillis();
sortBySchoolById1(students1);
end = System.currentTimeMillis();
System.out.println("Two stable sorts took " + (end - start)
+ " milliseconds.");
start = System.currentTimeMillis();
sortBySchoolById2(students2);
end = System.currentTimeMillis();
System.out.println("One stable sort with a two criteria comparator took "
+ (end - start) + " milliseconds.");
start = System.currentTimeMillis();
sortBySchoolById3(students3);
end = System.currentTimeMillis();
System.out.println("Bucket sort took " + (end - start)
+ " milliseconds.");
if (!(students1.equals(students2) && students2.equals(students3))) {
System.out.println("Fix me: One or more sorts are incorrect.");
}
writeToFile(students3, "studentsSorted.txt");
}
}
public class Student {
private int id;
private String name;
private String school;
public Student (int id, String name, String school) {
this.id = id;
this.name = name;
this.school = school;
}
int getId() {
return id;
}
String getSchool() {
return school;
}
@Override
public String toString() {
return name + "," + id + "," + school;
}
}
Explanation / Answer
package chegg.generics;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;
public class Project4 {
/**
* Read students from file into a list
*
* @param filename
* @return the list of students
*/
static ArrayList<Student> readFromFile(String filename) {
ArrayList<Student> students = new ArrayList<Student>();
try (Scanner in = new Scanner(new File(filename))) {
while (in.hasNextLine()) {
String[] fields = in.nextLine().split(",");
students.add(new Student(Integer.parseInt(fields[1]),
fields[0], fields[2]));
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
return students;
}
/**
* Write the students to a file
*
* @param students
* @param filename
*/
static void writeToFile(ArrayList<Student> students, String filename) {
try (FileWriter out = new FileWriter(filename)) {
for (Student s : students) {
out.write(s.toString());
out.write(" ");
}
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* Sorts the students list by school. Same school students are sorted by ID.
*
* Performs two stable sorts with different criteria. One sort and then
* another sort.
*
* @param students
*/
static void sortBySchoolById1(ArrayList<Student> students) {
TreeMap<Integer, ArrayList<Student>> map = new TreeMap<Integer, ArrayList<Student>>();
for (Student student : students) {
if (!map.containsKey(schoolToIndex(student.getSchool()))) {
ArrayList<Student> list = new ArrayList<Student>();
list.add(student);
map.put(new Integer(schoolToIndex(student.getSchool())), list);
} else {
ArrayList<Student> list = map.get(schoolToIndex(student
.getSchool()));
list.add(student);
}
}
for (Entry<Integer, ArrayList<Student>> mapEntry : map.entrySet()) {
Collections.sort(mapEntry.getValue(), new SortById());
}
System.out.println("Two Stable sorts result : "+map);
}
/**
* Sorts the students list by school. Same school students are sorted by ID.
*
* Performs only one sort that uses a comparator that takes both criteria
* into account.
*
* @param students
*/
static void sortBySchoolById2(ArrayList<Student> students) {
Collections.sort(students, new SortBySchoolAndId<Student>());
System.out.println(" One stable sorts result : "+students);
}
/**
* Use this function in your bucket sort
*
* Return the bucket index for each school (schools in alphabetical order)
*
* "UCB", "UCD", "UCI", "UCLA", "UCM", "UCSD", "UCSF" 0 1 2 3 4 5 6
*
* @param school
* @return the bucket index
*/
private static int schoolToIndex(String school) {
switch (school) {
case "UCB":
return 0;
case "UCD":
return 1;
case "UCI":
return 2;
case "UCLA":
return 3;
case "UCM":
return 4;
case "UCSD":
return 5;
case "UCSF":
return 6;
default:
System.err.println("Unknown school " + school);
return -1;
}
}
/**
* Sorts the students list by school. Same school students are sorted by ID.
*
* Places all the students of the same school into an individual bucket and
* sorts each bucket separately.
*
* @param students
*
*/
static void sortBySchoolById3(ArrayList<Student> students) {
final int NUM_SCHOOLS = 7;
// an array of lists. Each element is a reference to a list.
ArrayList<Student>[] buckets = (ArrayList<Student>[]) new ArrayList[NUM_SCHOOLS];
// Your code here
}
public static void main(String[] args) {
ArrayList<Student> students1 = readFromFile("d://students.txt");
System.out.println("Actual List contents :" + students1.toString());
// make 2 other copies so we don't have to read the file again
ArrayList<Student> students2 = new ArrayList<Student>(students1);
ArrayList<Student> students3 = new ArrayList<Student>(students1);
// let's time the three sorts for fun. Not really that accurate.
long start, end;
start = System.currentTimeMillis();
sortBySchoolById1(students1);
end = System.currentTimeMillis();
System.out.println("Two stable sorts took " + (end - start)
+ " milliseconds.");
start = System.currentTimeMillis();
sortBySchoolById2(students2);
end = System.currentTimeMillis();
System.out
.println("One stable sort with a two criteria comparator took "
+ (end - start) + " milliseconds.");
start = System.currentTimeMillis();
sortBySchoolById3(students3);
end = System.currentTimeMillis();
System.out.println("Bucket sort took " + (end - start)
+ " milliseconds.");
if (!(students1.equals(students2) && students2.equals(students3))) {
System.out.println("Fix me: One or more sorts are incorrect.");
}
writeToFile(students3, "studentsSorted.txt");
}
}
class Student {
private int id;
private String name;
private String school;
public Student(int id, String name, String school) {
this.id = id;
this.name = name;
this.school = school;
}
int getId() {
return id;
}
String getSchool() {
return school;
}
@Override
public String toString() {
return name + "," + id + "," + school;
}
}
class SortBySchoolAndId<Student> implements Comparator<chegg.generics.Student> {
@Override
public int compare(chegg.generics.Student o1, chegg.generics.Student o2) {
if (o1.getSchool().compareTo(o2.getSchool()) != 0) {
return o1.getSchool().compareTo(o2.getSchool());
}
return Integer.compare(o1.getId(), o2.getId());
}
}
class SortById implements Comparator<chegg.generics.Student> {
@Override
public int compare(Student o1, Student o2) {
if (o1.getId() == o2.getId()) {
return 0;
} else if (o1.getId() < o2.getId()) {
return -1;
} else {
return 1;
}
}
}
Description :
As given in above question, i have added two mehtod implementation
1. Two sorts alogirithum ( See method sortBySchoolById1() ) : -
Here first level sorts done on school, which is automatically handles by treemap. Check the integerschool id and each school id in tree map, one corresponding list which is leter on sorted by collection.sort() method.
SortById<Student> class is added for the same.
2. Single sort alogorithum
here both the sorting is handled in one go.Please check the class SortBySchoolAndId<Student>
I have added two classes as inner class. You can sperate it out using public keyword and maintian in sperate file.
please let me know if you face any chanllanges to make understanding on above code.
Input file ( input.txt) : place this file in same directory where this program is placed.
-----------
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
Output
-----------
Actual List contents :[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]
Two Stable sorts result :
{0=[Joe Paarmann,3,UCB, Otha Baloy,5,UCB], 1=[Alton Hamblet,1,UCD, Jessie Merle,7,UCD, Lawanda Doell,9,UCD], 2=[Alva Zajicek,4,UCI], 3=[Chester Kemfort,2,UCLA, Alice Mines,6,UCLA]}
Two stable sorts took 5 milliseconds.
One stable sorts result :
[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]
One stable sort with a two criteria comparator took 2 milliseconds.
Bucket sort took 0 milliseconds.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.