Start learning free

LESSON 563 OF 569 · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

Sort Your Own Objects in Java: Comparable and compareTo

Practice O(n log n) Read the full explanation

A language can sort numbers and strings on its own: it already knows which of two of them comes first. For objects of your own class it doesn't, until the class tells it. Every language has a way for a class to say how two of its objects compare. Once a class has it, the language's own sort can sort a list of those objects, with no comparison written at the call.

Write:

  • a class Student, created by Student(name, grade), that can compare itself with another student: a student comes first if their grade is higher; when two grades are equal, the name that comes first in alphabetical order (A to Z) comes first;
  • a method rankStudents(students) in the class Solution, which sorts the students with your language's own sort, using that comparison, and returns their names in that order.

In Java, Student implements Comparable<Student>: its method compareTo(other) returns a negative number when this student comes first, a positive number when other does, and 0 when they are equal. Collections.sort uses it.

Don't write your own sorting loop. The program also checks your comparison directly: for each two neighbours in the list you return, it asks Student whether the first one comes before the second.

 

Example 1:

Input: students = [("Ana", 90), ("Bob", 85), ("Cid", 90)]
Output: Ana Cid Bob
Explanation: Ana and Cid have the highest grade, 90. They tie, so their names decide: Ana comes before Cid.
Bob, with 85, comes last.

Example 2:

Input: students = [("Eve", 55), ("Dan", 100), ("Bea", 0), ("Cal", 99)]
Output: Dan Cal Eve Bea
Explanation: All the grades are different, so only the grades decide, from 100 down to 0.

Example 3:

Input: students = [("Max", 88), ("Leo", 88), ("Anna", 88), ("Ann", 88)]
Output: Ann Anna Leo Max
Explanation: Everyone has the same grade, so the list is in alphabetical order.
"Ann" comes before "Anna": when one name is the start of the other, the shorter one comes first.

 

Constraints:

  • There are 1 to 100 students.
  • 0 <= grade <= 100
  • A name has 2 to 10 letters: a capital letter, then lowercase letters. No two students have the same name.
Note:

The language's sort takes O(n log n) comparisons for n students, and each comparison takes constant time.

STEP 1 OF 9
    Ctrl + Enter to check

    JAVA · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

    Sort Your Own Objects in Java, explained

    Problem overview

    Java can sort numbers and strings on its own because it knows which of two of them comes first. For objects of your own class it doesn't, until the class says how two of its objects compare. In Java a class says so by implementing Comparable. After that, Collections.sort can sort a list of those objects with no comparison written at the call.

    You write:

    • a class Student, created with Student(name, grade), that implements Comparable<Student>. A student comes first if the grade is higher. When the grades are equal, the name that comes first alphabetically comes first;
    • rankStudents(students) in Solution, which sorts the students with Collections.sort and returns their names in that order.

    For Ana (90), Bob (85) and Cid (90) the result is [Ana, Cid, Bob]. Ana and Cid tie on 90, so their names decide, and Bob's 85 puts him last.

    How compareTo works

    The one method of Comparable<Student> is compareTo(Student other). It returns a number:

    • negative when this student comes first;
    • positive when other comes first;
    • 0 when they are equal.

    The sort uses only the sign of the result. For the students above, the calls give these values:

    ana.compareTo(cid)  ->  -2
cid.compareTo(ana)  ->   2
ana.compareTo(ana)  ->   0
bob.compareTo(ana)  ->   5

    The numbers' sizes don't matter, only that they are negative, positive or zero. Ana comes before Cid, Cid after Ana, and Bob, with the lower grade, after Ana.

    Approach: two keys, compared in order

    The ranking has two rules: first the grade, highest first, then the name, A to Z. compareTo checks them in that order:

    1. If the grades differ, the grade decides. Returning other.grade - grade is negative exactly when this student's grade is bigger, which is what puts higher grades first. Note the order of the subtraction: it is reversed on purpose, because a normal ascending sort would use grade - other.grade.
    2. If the grades are equal, the names decide. String is itself Comparable, so name.compareTo(other.name) already gives a negative number when name is earlier alphabetically.

    Because the names are all different, two distinct students never compare as 0.

    Step by step

    1. Declare the fields public String name; and public int grade;. rankStudents reads name later.
    2. Store the parameters in the constructor with this.name = name; and this.grade = grade;.
    3. Compare the grades. If they differ, return other.grade - grade.
    4. Compare the names when the grades are equal: return name.compareTo(other.name).
    5. Sort in rankStudents with Collections.sort(students), with no comparator. Java finds compareTo because Student is Comparable.
    6. Collect the names in a new ArrayList<> by looping over the sorted students, and return it.

    The solution in Java

    class Student implements Comparable<Student> {
    public String name;
    public int grade;

    public Student(String name, int grade) {
        this.name = name;
        this.grade = grade;
    }

    @Override
    public int compareTo(Student other) {
        if (grade != other.grade) {
            return other.grade - grade;
        }
        return name.compareTo(other.name);
    }
}

class Solution {
    public List<String> rankStudents(List<Student> students) {
        Collections.sort(students);
        List<String> names = new ArrayList<>();
        for (Student student : students) {
            names.add(student.name);
        }
        return names;
    }
}

    Details worth knowing

    • No sorting loop. The sort is Java's own, and Student only supplies the comparison. If Student did not implement Comparable, the call Collections.sort(students) would not compile: the compiler reports that no suitable sort method was found for the list.
    • Sorting changes the list. Collections.sort rearranges the list it receives in place. rankStudents then builds a separate list of names.
    • String comparison is by characters. "Ann".compareTo("Anna") is negative, because when one name is the start of the other, the shorter one comes first. In the third example Ann comes before Anna.
    • Subtraction is safe here. Grades are between 0 and 100, so other.grade - grade can't overflow. For values over a wider range, Integer.compare(other.grade, grade) is the safe form.

    Sorting by hand-made rules

    Once compareTo exists, the rule travels with the class. Any code that sorts a list of students gets the same order, whether it uses Collections.sort or another library method that relies on Comparable. Here the list starts as Bob, Cid, Ana:

    List<Student> students = new ArrayList<>(List.of(bob, cid, ana));
Collections.sort(students);
for (Student s : students) System.out.println(s.name + " " + s.grade);

    Ana 90
Cid 90
Bob 85

    The list must be modifiable for Collections.sort to work, which is why it is wrapped in a new ArrayList here: the list returned by List.of is fixed, and sorting it throws an UnsupportedOperationException.

    Complexity

    Sorting n students takes O(n log n) comparisons, and each compareTo takes constant time (the names have at most 10 letters). Collecting the names is one more pass of O(n). The list of names takes O(n) extra space.

    In the second example every grade is different, so the grades alone decide, from 100 down to 0, and the names are never compared. In the third, every grade is 88, so the order is purely alphabetical.

    Testing

    StudentsResult
    Ana 90, Bob 85, Cid 90[Ana, Cid, Bob]
    Eve 55, Dan 100, Bea 0, Cal 99[Dan, Cal, Eve, Bea]
    Max 88, Leo 88, Anna 88, Ann 88[Ann, Anna, Leo, Max]

    Common mistakes

    • Subtracting in the wrong order. grade - other.grade ranks the lowest grade first.
    • Writing your own sorting loop. The exercise is to let the language's sort do the work, using your comparison.
    • Returning a boolean. compareTo returns an int. A "true or false" answer can't say "before", "after" and "equal".
    • Using == on names. It compares references, not contents. Use name.compareTo(other.name) or equals.
    • Forgetting the tie-break. If you only compare grades, students with equal grades come out in whatever order they started in (the sort is stable, so they keep their original order), not alphabetically.
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free