I have recently been working to better my understanding of sorting algorithms and their relationship to different types of input. Currently, I'm working on a Student Management program where each student has three parameters: Last Name, GPA, and User ID (String, double, int). They are each stored in a Student class with those three parameters, and there are DOZENS of students (a key feature of the program is to input, remove, and update students).

My question is: using the major sorting algorithms (mergesort, quicksort, etc.), what is the best way to sort my list of students by each parameter? For instance, what is the best way to perform a mergesort to sort the list by GPA? Or to use quicksort to sort the list by last name?

Essentially my question boils down to...I can sort these objects if they didn't have three parameters (writing a mergesort to sort 100 numbers is very easy for me). How do I manage the other two parameters and make sure they're accessible after the sort?

• java
• sorting
• object

The way this is done in Java is to use different Comparators. Then you say:

Collections.sort(list, new NameComparator());

Or

Collections.sort(list, new GpaComparator());

These comparators use different fields to define the order between two elements.

For example, Name Comparator might be:

class NameComparator implements Comparator< Student> {
    @Override public int compare(Student left, Student right) {
        return left.getName().compareTo(right.getName());
    }
}

And GpaComparator might be

class GpaComparator implements Comparator< Student> {
    @Override public int compare(Student left, Student right) {
        if (left.getGpa() < right.getGpa()) {
            return -1;
       } else if (left.getGpa() > right.getGpa()) {
            return 1;
       } else {
           return 0;
     }
 }

I would recommend implementing the Comparable interface in your Student Class like this

public class Student implements Comparable {
   public int compareType; //you can make this an enum if you want
   ...

   public int compareTo(Object o) {
       if(compareType == 0) 
         return gpaCompareTo(o);
       else if(compareType == 1)
         return nameCompareTo(o);

       return idCompateTo(o); 
   }

   public int gpaCompareTo(Object o) {
       //implement your gpaCompareTo
   }

   public int nameCompareTo(Object o) {
       //implement your nameCompareTo
   }

   public int idCompareTo(Object o) {
       //implement your idCompareTo
   }
}

And then use a built-in sort like

List<Student> list = new ArrayList<Student>();
...
Collections.sort(list);

Or you can not implement Comparable and design your own comparators

public class MyComparator implements Comparator<Student> {

   public int compare(Student o1, Student o2) {
      //implement the comparator
   }

   public boolean equals(Object o) {
      //implement the equals 
   }
}

Then you can use the other Collection's sort method

Collections.sort(list, MyComparator);

The typical way to do this is to write a generic sorting algorithm on any type that accepts a Comparator, and then to write different Comparators to sort by different fields.

This is probably off topic, but if you want to try something cool, the JDK 8 Lambda Preview offers a few cool ways to define comparators using Lamda expressions and method references.

Let's say we have a class:

class Jedi  {
   private final String name;
   private final int age;
   //...
}

And then a collection of them:

List<Jedi> jediAcademy = asList(new Jedi("Obiwan",80), new Jedi("Anakin", 30));
sort(jediAcademy, (j1, j2) -> j1.getAge() > j2.getAge() ? 1 : j1.getAge() < j2.getAge() ? -1 : 0);
System.out.println(jediAcademy); //Anakin, Obiwan

Or with method references, supposing Jedi has method that behaves as a comparator (same signature)

class Jedi  {
  public static int compareByAge(Jedi first, Jedi second){
     return first.age > second.age ? 1 : first.age < second.age ? -1 : 0;
  }
   //...
}

Which could be used as follows to generate a comparator by using a method reference:

List<Jedi> jediAcademy = asList(new Jedi("Obiwan",80), new Jedi("Anakin", 30));
sort(jediAcademy, Jedi::compareByAge);
System.out.println(jediAcademy);//Anakin, Obiwan

It's really no different than sorting numbers, except that in this case your "digits" are the three fields of your users, the value of each digit is constrained by the values of each field, and the order of the fields determines the sort ranking.

To be a bit more specific, you have a Tupple with 3 fields: <GPA, Last Name, User ID>, and lets assume that you want to sort by GPA, and then Last Name, and the User ID.

In the same way that 219 is sorted above 139 (ie. the "hundreds" digit has a higher value even though the "tens" digit is lower), a tupple like <3.75, Jones, 5> will be sorted above <3.0, Adams, 2> because the "GPA digit" (which is more significant) has a higher value, even though the "last name digit" is lower (eg. Jones is "lower" than Adams).

Use multiple comparators

class Student
{

        String lastName;
        dounle GPA;
        int userId


    static Comparator<Student> getStudentLastNameComparator() {
        return new Comparator<Student>() {

            @Override
            public int compare(Student Student1, Student Student2) {
                return Student1.getlastName().compareTo(Student2.getlastName());
            }
            // compare using Student lastName
        };
    }

    static Comparator<Student> getStudentGPAComparator() {
        return new Comparator<Student>() {

            @Override
            public int compare(Student Student1, Student Student2) {
                if(Student1.GPA < Student2.GPA)
                    return 1;
                else
                    return -1;
            }
            // compare using Student GPA
        };
    }

    static Comparator<Student> getStudentUserIdComparator() {
        return new Comparator<Student>() {

            @Override
            public int compare(Student Student1, Student Student2) {
                if(Student1.userId < Student2.userId)
                    return 1;
                else
                    return -1;
            }
            // compare using Student userId
        };
    }
}