Comparable и сортировка

В конце вечера гардеробщик раскладывает забытые шапки по размеру. Таблица всех размеров ему не нужна. Достаточно взять две шапки и решить, какая из них встанет левее. Повторяя такие сравнения, он разложит любую гору шапок.

Метод Collections.sort работает так же: он сравнивает элементы попарно и переставляет их. Числа и строки Java сравнивать умеет сама:

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]
    }
}

Давайте разберём программу по строкам:

1. Collections — класс из java.util с готовыми методами для коллекций, и sort — один из них.
2. Списки скопированы из List.of в ArrayList: Collections.sort переставляет элементы в самом списке, а неизменяемый список переставить нельзя.
3. Числа встают по возрастанию: [1, 2, 3].
4. Строки встают по кодам символов. Заглавные буквы идут раньше строчных, поэтому "anna" со строчной буквы оказалась в конце.

Естественный порядок и compareTo

Порядок, в котором тип сортируется сам, называют естественным порядком. Его задаёт метод compareTo из интерфейса Comparable, и String с Integer этот интерфейс реализуют. Вызов a.compareTo(b) отвечает на вопрос гардеробщика числом:

• отрицательное — a встаёт раньше b;
• ноль — по порядку они равны;
• положительное — a встаёт после b.

Важен только знак, а не само число. Например, "Anna".compareTo("Boris") возвращает -1, а "Vera".compareTo("anna") — -11: строки сравниваются по первому несовпавшему символу, а коды 'V' и 'a' — это 86 и 97. Поэтому результат проверяют через < 0 и > 0, а не сравнивают с -1 и 1.

На собеседовании часто спрашивают, что возвращает compareTo. Ответ: число со знаком, а не true или false.

Свой класс: Comparable

Свой класс Java сортировать не умеет: она не знает, по какому полю ставить игроков, по имени или по очкам. Правило пишете вы. Класс реализует интерфейс Comparable и его единственный метод compareTo:

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

Разберём объявление по частям:

1. implements Comparable<Player> — у интерфейса тоже есть параметр типа: игрок сравнивается с игроком.
2. compareTo(Player o) сравнивает этого игрока, this, с другим, o.
3. Integer.compare(score, o.score) даёт отрицательное число, если очков у this меньше, ноль при равенстве и положительное, если больше. Значит, игроки встанут по возрастанию очков.

Теперь список игроков сортируется:

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 вызывает compareTo для пар игроков и ставит первым Бориса с 10 очками, за ним Веру и Анну. Чтобы отсортировать по убыванию, поменяйте аргументы местами: Integer.compare(o.score, score). Массив объектов сортирует Arrays.sort из темы о массивах. Он вызывает тот же compareTo, так что массив Player[] встанет в том же порядке.

Здесь картинка с шапками неточна. Гардеробщик может завтра разложить шапки по цвету, а compareTo у класса один. Он задаёт только один порядок — естественный.

Частая ошибка

Сортируют список записей, у которых нет implements Comparable<Player>:

Collections.sort(team); // ✗

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

Программа не компилируется: Collections.sort с одним аргументом принимает только список элементов, которые умеют сравниваться сами, то есть реализуют Comparable. Добавьте в объявление implements Comparable<Player> и метод compareTo, как выше.

Главное

• Collections.sort(list) переставляет элементы в самом списке: числа встают по возрастанию, строки — по кодам символов, заглавные раньше строчных.
• Естественный порядок задаёт compareTo из интерфейса Comparable: отрицательное число — this раньше, ноль — равны, положительное — позже.
• Свой класс сортируется, когда реализует Comparable и compareTo; удобно возвращать Integer.compare(score, o.score).
• Arrays.sort сортирует массив объектов через тот же compareTo, а без Comparable вызов Collections.sort не компилируется.