Sorting in Java comes in two flavours. A Comparable implementation says how its own objects should be ordered, and that is baked into the class and available everywhere. A Comparator is a separate object that holds a rule that you pass to a sort, so the same list can be ordered differently for the different purposes without changing the class.
The previous lesson in this module covered "How Does HashSet Enforce Uniqueness so Fast?", and this lesson is the last one in the Collections Framework module.
What is the difference between Comparable and Comparator?
Both of them end up in the same place. The sort asks one object to compare itself with another and it gets a negative number, a zero or a positive number back. The difference is where the rule lives. The interface Comparable puts it inside the class, so there is exactly one natural order and it applies to every list of that type. The interface Comparator keeps it outside, so you can have as many orders as you like, by surname, by score, reversed or case-insensitively, and you pass the one that you need to the sort call.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class SortBasicsDemo {
public static void main(String[] args) {
List<String> words = new ArrayList<>(List.of("pear", "Apple", "fig", "banana"));
System.out.println("start: " + words);
words.sort(Collections.reverseOrder());
System.out.println("reversed: " + words);
words.sort(Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));
System.out.println("shortest first, then alphabetically: " + words);
}
}The output is this.
start: [pear, Apple, fig, banana]
reversed: [pear, fig, banana, Apple]
shortest first, then alphabetically: [fig, pear, Apple, banana]Three tools are doing the work here. The call Collections.reverseOrder() gives you the opposite of the natural order without needing to write a lambda. The call Comparator.comparingInt builds a comparator from a key extractor, in this case the string length. And thenComparing chains a second rule that only matters when the first one says that the elements are equal. That is why "fig" comes before "pear", and why the three-letter words are ordered alphabetically among themselves.
How do you sort the objects by several fields?
You chain the rules. Each thenComparing call adds a tie-breaker, and the chain is read from the left to the right as "sort by this first, and then by this when the first says that they are equal".
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class SortByFieldDemo {
record Student(String surname, String firstName, int mark) {
}
public static void main(String[] args) {
List<Student> students = new ArrayList<>(List.of(
new Student("Okafor", "Chidi", 71),
new Student("Adeyemi", "Bola", 88),
new Student("Okafor", "Amaka", 88)));
students.sort(Comparator.comparing(Student::surname)
.thenComparing(Student::firstName));
for (Student student : students) {
System.out.println(student.surname() + ", " + student.firstName() + " - " + student.mark());
}
students.sort(Comparator.comparingInt(Student::mark).reversed()
.thenComparing(Student::surname));
System.out.println("by highest mark first:");
for (Student student : students) {
System.out.println(student.surname() + ", " + student.firstName() + " - " + student.mark());
}
}
}The output is this.
Adeyemi, Bola - 88
Okafor, Amaka - 88
Okafor, Chidi - 71
by highest mark first:
Adeyemi, Bola - 88
Okafor, Amaka - 88
Okafor, Chidi - 71The first sort groups by the surname and then orders the two Okafor students by the first name, so Chidi and Amaka land in a predictable order. The second sort puts the highest mark first with reversed() and uses the surname as the tie-breaker, which is why the two students on 88 are listed as Adeyemi then Okafor rather than in an arbitrary order.
How do you write a comparator as a class instead of a lambda?
You implement the interface Comparator and you give it a compare method. It is more lines than a lambda, and it earns them when the rule is reused, when it carries a name that explains itself, or when it needs to be configurable.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class CustomComparatorDemo {
static class CaseInsensitive implements Comparator<String> {
@Override
public int compare(String left, String right) {
return left.compareToIgnoreCase(right);
}
}
public static void main(String[] args) {
List<String> words = new ArrayList<>(List.of("apple", "Banana", "cherry"));
words.sort(new CaseInsensitive());
System.out.println("case insensitive: " + words);
words.sort(Comparator.naturalOrder());
System.out.println("natural order puts capitals first: " + words);
}
}The output is this.
case insensitive: [apple, Banana, cherry]
natural order puts capitals first: [Banana, apple, cherry]The difference between the two lines is the whole reason that the custom comparators exist. The natural order compares the character by character, and the capital letters sort before the lower-case ones, so "Banana" jumps ahead of "apple". A case-insensitive comparator ignores the case, which is what a person usually means when they sort a list of names.
Where else do the comparators work?
Anywhere a collection has to keep itself in order takes a comparator, and not just the sort method. A TreeSet or a TreeMap uses one to decide which element comes next, and that comparator keeps working for every future insertion too.
import java.util.Comparator;
import java.util.NavigableSet;
import java.util.TreeSet;
public class SortedSetDemo {
record Task(String label, int priority) {
}
public static void main(String[] args) {
Comparator<Task> byPriority = Comparator.comparingInt(Task::priority)
.thenComparing(Task::label);
NavigableSet<Task> queue = new TreeSet<>(byPriority);
queue.add(new Task("write docs", 2));
queue.add(new Task("fix login", 1));
queue.add(new Task("ship release", 3));
for (Task task : queue) {
System.out.println(task.priority() + " - " + task.label());
}
System.out.println("the highest priority task is: " + queue.last().label());
System.out.println("remove it: " + queue.pollLast().label());
System.out.println("what is left: " + queue.size() + " task(s)");
}
}The output is this.
1 - fix login
2 - write docs
3 - ship release
the highest priority task is: ship release
remove it: ship release
what is left: 2 task(s)The set keeps itself sorted as the items arrive, so you never have to call a sort method. That comes with two obligations. The elements that compare equal are treated as the same element, so a set of tasks with the identical priorities and the labels would keep only the first one that you added. And the comparator must give a consistent answer, or the structure can end up in a state that its own methods cannot navigate.
Which rules keep a comparator honest?
- Return a negative number, a zero or a positive number. Never rely on the exact magnitude, and never subtract the two values to produce it, because the subtraction overflows on the large numbers.
- Be consistent. The same pair of elements must always compare the same way, or the sorted collections misbehave.
- Think about the equality. If your comparator says that two objects are equal while their equals says otherwise, then a set or a map built on that comparator will treat them as one element and then fail to find one of them again.
- Handle the nulls deliberately with Comparator.nullsFirst or
nullsLastrather than by accident. The natural comparison throws a NullPointerException when it meets a null. - Sorting a list does not modify its size and it does not lose the elements, and the sort is stable, so the elements that compare equal keep their original relative order.
One habit is worth forming early. Reach for Comparator.comparing and for the chaining methods before you write a lambda by hand. They are shorter, they read better at a glance, and the type inference does the work that you would otherwise do by casting.
An ordering cheat sheet
- The natural order comes from Comparable and it is fixed for the class, while a Comparator supplies an order on the side.
- The calls List.sort and Collections.sort reorder a list in place, and Arrays.sort does the same for an array.
- The call Comparator.comparing builds a rule from a key,
thenComparingadds the tie-breakers, and reversed flips a rule. - The tree sets and the tree maps keep themselves sorted by using the same comparators.
- A comparator that disagrees with equals breaks the sets and the maps, so keep the two ideas aligned.
Try it yourself: create a list of eight book titles with the authors, and then sort it three ways. Sort it by the author, by the title length, and by the title ignoring the case. Print the list after each sort, so that you can see the orders differ. Then write a comparator class that sorts by the author and breaks the ties by the title, and use it to sort the same list once more.