Comparator

In the previous theme, Collections.sort put strings in order by character codes, and objects of your own class in the order their compareTo decided. That is the natural order, and a class has only one. But what if the same list of words must be sorted by length? You cannot rewrite compareTo in String: the class is not yours.

Back to the conveyor belt. A sorting station stands on it: the worker takes two boxes and decides which one goes first. The order printed on the box itself is the Comparable from the previous theme. A card with a comparison rule, for example "shorter first", is handed over separately, and the station can get any one of them. In Java, such a card is called a Comparator:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> words =
            new ArrayList<>(List.of("kiwi", "fig", "banana"));
        Comparator<String> byLength =
            (a, b) -> Integer.compare(a.length(), b.length());
        words.sort(byLength);
        System.out.println(words); // [fig, kiwi, banana]
    }
}

Let's go through the program line by line:

1. Comparator<String> byLength is the card "how to compare two strings". The Comparator interface has one abstract method, compare(a, b), so it is written as a lambda with two parameters.
2. Integer.compare(a.length(), b.length()) compares the lengths of the two words.
3. words.sort(byLength) sorts the list itself by this card. The method returns nothing and changes words in place.
4. The output is [fig, kiwi, banana]: from the shortest word to the longest.

The compare method

A comparator is an object of type Comparator that compares two values. Its compare(a, b) method answers with a number, like compareTo from the previous theme:

• a negative number: a goes before b;
• zero: a and b are equal for this order;
• a positive number: a goes after b.

The answer of Integer.compare works exactly this way. Subtracting a - b overflows on large numbers, like the odometer from the operators theme, so numbers are compared with Integer.compare.

Both list.sort(c) and Collections.sort(list, c) can sort by a comparator. Both change the list itself and return nothing.

Comparator.comparing

More often the card is not written by hand but built from a key, the thing to compare. Comparator.comparing(String::length) takes the length out of each string and compares the lengths, which is what byLength does. A ready comparator can be reversed or extended with a second rule.

reversed

reversed() returns a new comparator with the opposite order: from the longest word to the shortest. The comparator it was called on does not change.

words.sort(Comparator.comparing(String::length));
System.out.println(words); // [fig, kiwi, banana]
words.sort(Comparator.comparing(String::length).reversed());
System.out.println(words); // [banana, kiwi, fig]

thenComparing

When two values are equal by the first rule, the second rule decides their order, thenComparing:

List<String> names = new ArrayList<>(List.of("Zoe", "Anna", "Max", "Bo"));
names.sort(Comparator.comparing(String::length)
    .thenComparing(Comparator.naturalOrder()));
System.out.println(names); // [Bo, Max, Zoe, Anna]

Let's go through it:

1. The first rule is length: Bo is the shortest, Anna the longest.
2. Zoe and Max have three letters each, and the first rule cannot tell them apart.
3. Comparator.naturalOrder() is the natural order of strings, the same compareTo that compares character codes. For Max and Zoe that is plain alphabetical order, and Max goes first.

Interviewers like to ask how Comparable differs from Comparator. The answer: Comparable gives a class one natural order from the inside, through compareTo. A Comparator is a separate object, and one class can have as many orders as you like without touching the class itself.

This is where the station picture is inaccurate. Other stations handle each box as it rides past, but sorting needs all the boxes at once. So sort rearranges the whole list, and the comparator only answers which of two boxes comes first.

Common mistake

A lambda was passed to comparing, and the order was reversed right away:

words.sort(Comparator.comparing(w -> w.length()).reversed()); // ✗

error: cannot find symbol

The program does not compile. The compiler works out the type of the parameter w from where the lambda goes.

Without .reversed(), the comparator would go straight into words.sort, and w would be a string. Here, though, the result of comparing goes to reversed() first, and comparing knows nothing about the list of strings. So w gets the type Object, and Object has no length() method; the next line of the message says exactly that: location: variable w of type Object. The fix is the method reference String::length or a type in the lambda: (String w) -> w.length().

Key points

• A Comparator is a separate comparison object: compare(a, b) returns a negative number, zero or a positive number.
• Comparable gives a class one natural order, while one class can have as many comparators as you like.
• Comparator.comparing(key) builds a comparator from a key, reversed() reverses the order, thenComparing breaks ties.
• list.sort(c) sorts the list itself and returns nothing.