Comparable and sorting

At the end of the evening, the attendant sorts the forgotten hats by size. A table of all the sizes is not needed. It is enough to take two hats and decide which one goes further left. By repeating such comparisons, the attendant can sort any pile of hats.

The method Collections.sort works the same way: it compares elements in pairs and moves them around. Java can compare numbers and strings by itself:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(List.of(3, 1, 2));
        Collections.sort(nums);
        System.out.println(nums);  // [1, 2, 3]
        List<String> names = new ArrayList<>(List.of("Vera", "anna", "Boris"));
        Collections.sort(names);
        System.out.println(names); // [Boris, Vera, anna]
    }
}

Let's go through the program line by line:

1. Collections is a class from java.util with ready-made methods for collections, and sort is one of them.
2. The lists are copied from List.of into an ArrayList: Collections.sort moves the elements inside the list itself, and an immutable list cannot be rearranged.
3. The numbers line up in ascending order: [1, 2, 3].
4. The strings line up by character codes. Capital letters come before lowercase ones, so "anna", starting with a lowercase letter, ended up last.

Natural order and compareTo

The order in which a type sorts by itself is called its natural order. It is set by the method compareTo from the interface Comparable, and String and Integer implement this interface. The call a.compareTo(b) answers the attendant's question with a number:

• negative: a goes before b;
• zero: they are equal in order;
• positive: a goes after b.

Only the sign matters, not the number itself. For example, "Anna".compareTo("Boris") returns -1, and "Vera".compareTo("anna") returns -11: strings are compared by the first character that differs, and the codes of 'V' and 'a' are 86 and 97. So check the result with < 0 and > 0 instead of comparing it with -1 and 1.

Interviewers often ask what compareTo returns. The answer: a signed number, not true or false.

Your own class: Comparable

Java cannot sort your own class: it does not know which field to order players by, the name or the score. You write the rule. The class implements the interface Comparable and its only method, compareTo:

record Player(String name, int score) implements Comparable<Player> {
    @Override
    public int compareTo(Player o) {
        return Integer.compare(score, o.score);
    }
}

Let's take the declaration apart:

1. implements Comparable<Player>: the interface has a type parameter too, so a player is compared with a player.
2. compareTo(Player o) compares this player, this, with another one, o.
3. Integer.compare(score, o.score) gives a negative number if this has fewer points, zero if they are equal and a positive number if it has more. So the players line up by ascending score.

Now a list of players can be sorted:

List<Player> team = new ArrayList<>();
team.add(new Player("Anna", 30));
team.add(new Player("Boris", 10));
team.add(new Player("Vera", 20));
Collections.sort(team);
System.out.println(team.get(0)); // Player[name=Boris, score=10]

Collections.sort calls compareTo on pairs of players and puts Boris with 10 points first, then Vera and Anna. To sort in descending order, swap the arguments: Integer.compare(o.score, score). An array of objects is sorted by Arrays.sort from the arrays theme. It calls the same compareTo, so a Player[] array lines up in the same order.

Here the hats picture is not exact. Tomorrow the attendant may sort the hats by color, but a class has only one compareTo. It sets only one order, the natural one.

Common mistake

A list of records without implements Comparable<Player> is sorted:

Collections.sort(team); // ✗

error: no suitable method found for sort(List<Player>)

The program does not compile: Collections.sort with one argument accepts only a list of elements that can compare themselves, that is, that implement Comparable. Add implements Comparable<Player> and the compareTo method to the declaration, as above.

Key points

• Collections.sort(list) rearranges the elements in the list itself: numbers go in ascending order, strings by character codes, capitals before lowercase.
• Natural order is set by compareTo from the interface Comparable: a negative number means this goes first, zero means equal, positive means later.
• Your own class sorts once it implements Comparable and compareTo; returning Integer.compare(score, o.score) is convenient.
• Arrays.sort sorts an array of objects through the same compareTo, and without Comparable a call to Collections.sort does not compile.