Alternate Orders Are Comparator<T>

Before You Start

Check each box you can do from memory. A box you cannot check yet is not a problem; it points you to a quick refresher, not a grade.

• I can state what a natural order is and explain why a class can have at most one.
• I can write the implements declaration for a class that provides its own natural ordering.
• I can explain what implements requires a class to do (provide a body for every method in the interface).

See Natural Order Is implements Comparable&lt;T&gt; and review interface implementation in CSCD 210 if any box above is unchecked.

Try This First

A Player class already implements Comparable<Player> (ordering by last name). You now need to sort an array of players by team name, then by games played. Before reading further, decide: should you (a) modify Player.compareTo, (b) add a method compareToByTeam(Player other) to Player, or (c) write a separate class?

Write your choice and a one-sentence justification.

What You Need To Walk In With

A Comparator<T> lives outside the type it compares. The type being sorted does not change. You can write any number of comparators for the same type and choose among them at each call site. This is the key difference from Comparable<T>, where the comparison logic lives inside the class and there is only one of them.

The main thing to remember is that Comparator<T> requires two parameters (compare(T a, T b)) and lives in a separate class. Everything else follows from that: you can identify a comparator class in a directory listing by its name and package, and you can explain why alternate orderings belong there rather than as extra methods on the type itself. You can: name the method Comparator<T> requires and its exact signature, distinguish compare(T a, T b) from compareTo(T other) by counting parameters, predict what Arrays.sort(arr, comparatorInstance) does compared to Arrays.sort(arr), and choose whether a new ordering belongs in compareTo or in a new Comparator class.

How It Works

The Comparator interface at a glance

Comparator<T> is a one-method interface (ignoring default methods). Its single required method is:

int compare(T a, T b)

Returns a negative integer, zero, or a positive integer as a is less than, equal to, or greater than b in the ordering this comparator defines. (Java 25 Comparator docs)

The F19 Lab 1 example

This lab is the canonical demonstration of the Comparable/Comparator dual in this course. The Player type has a natural order (its own compareTo). The cscd211Comparators/ package adds three separate ordering objects for the same type:

cscd211Comparators/
    TeamComparator.java          // orders Player by team name
    PositionComparator.java      // orders Player by position
    GamesPlayedComparator.java   // orders Player by games played (ascending)

Player.java does not change. At the call site, the caller picks whichever ordering it needs:

// natural order: sort by last name
Arrays.sort(players);

// alternate order: sort by team
Arrays.sort(players, new TeamComparator());

// alternate order: sort by games played
Arrays.sort(players, new GamesPlayedComparator());

Each comparator class is entirely self-contained. Adding a fourth ordering (say, by salary) requires writing one new file and zero modifications to Player.java.

The signature difference

The two interfaces look similar but are not interchangeable:

A Comparator<Player> class has no Player receiver in the comparison. Both Player objects arrive as explicit arguments.

Worked Example: Predict Then Check

The following excerpt is from a client class that has both sorting options available:

Player[] roster = { playerC, playerA, playerB };

// sort 1: natural order (last name)
Arrays.sort(roster);
System.out.println(Arrays.toString(roster));

// sort 2: by team name
Arrays.sort(roster, new TeamComparator());
System.out.println(Arrays.toString(roster));

Assume:

• playerA: lastName = "Adams", team = "Bears"
• playerB: lastName = "Burns", team = "Aces"
• playerC: lastName = "Chen", team = "Bears"

Predict what each println prints (just show the order of names).

Quick check

Common Misconceptions

Misconception 1: adding alternate orderings as extra methods on the type

Wrong mental model: “To sort by team I add compareToByTeam(Player other) on Player. To sort by games played I add compareToByGamesPlayed. Each ordering is just another method.”

Why it breaks: Arrays.sort(players, ???) expects a Comparator<Player> instance, not a method reference to compareToByTeam. Custom-named comparison methods are invisible to sort routines. The class fills with comparison methods that no standard API can call. Adding a fourth ordering later requires editing Player.java, recompiling everything that depends on it, and growing the class indefinitely.

How to correct: Each alternate ordering gets its own Comparator<Player> class. Player.java does not change. The caller passes the right comparator at the sort call site.

Source: Bloch, Effective Java, Item 14.

Quick check

Misconception 2: confusing the compare and compareTo signatures

Wrong mental model: “compare and compareTo are different names for the same operation, so I can use either signature in either context.”

Why it breaks on a small example: A Comparator<Player> written with one parameter:

public class PositionComparator implements Comparator<Player>
{
    @Override
    public int compare(final Player other)   // BUG: only one parameter
    {
        return this.getPosition().compareTo(other.getPosition());
    }
}

This does not compile: Comparator<Player> requires compare(Player a, Player b) with two parameters. The method above has the wrong signature and does not override anything. With @Override present, the compiler reports the error immediately.

How to correct: In a Comparator<T> class, always write compare(T a, T b) with two explicit parameters. In a Comparable<T> class, write compareTo(T other) with one parameter, comparing this to other.

Source: observation from nearly every quarter’s first Comparator lab.

Formal Definition and Interface Contract

From the Java 25 Comparator API:

A comparison function, which imposes a total ordering on some collection of objects. Comparators can be passed to a sort method (such as Collections.sort or Arrays.sort) to allow precise control over the sort order. Comparators can also be used to control the order of certain data structures (such as sorted sets or sorted maps), or to provide an ordering for collections of objects that don’t have a natural ordering.

int compare(T o1, T o2) -- Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

The same sign contract applies: negative means a before b, zero means equal, positive means a after b. The contract requirements are identical to those of compareTo (antisymmetry, transitivity, consistency).

Mental Model

Think of a Comparator<T> as a judge brought in from outside. The type being judged (Player, Book, Widget) does not change; it just presents itself to the judge. You can bring in any number of judges, one for each criterion, and swap them at the call site. The natural order (compareTo) is the type judging itself: one built-in criterion, always available, never swappable.

Connections

Within CSCD 210/211: The compare(T a, T b) signature and the compareTo(T other) signature are both covered in this lane. Implementing Comparator&lt;T&gt; as a Named Class explains how to write the named Comparator class in full. One Class, Many Comparators by Design revisits the F19 Lab 1 design to show how multiple comparators coexist with a natural order.

Looking back: Natural Order Is implements Comparable&lt;T&gt; established what a natural order is and why a class can have at most one. This lesson is the other half of the same dual.

Looking ahead: Implementing Comparator&lt;T&gt; as a Named Class covers the full named-class form for writing a Comparator. Anonymous-Class Syntax for Comparator and Writing a Comparator as a Lambda replace the named class with an anonymous inner class and then a lambda. Comparator.comparing by Key replaces all of those with the composable Comparator.comparing API.

Practice

Level 1

A directory listing shows:

cscd211Comparators/
    GamesPlayedComparator.java
    PositionComparator.java
    TeamComparator.java

Without opening the files, answer: what interface does each class most likely declare to implement? What is the type parameter?

Level 2

A Book class already implements Comparable<Book> (ordering by ISBN). You must add support for sorting books by page count (ascending). Identify which of these three approaches is correct, and explain why the other two are wrong:

(a) Modify Book.compareTo to order by page count.

(b) Add a method compareByPages(Book other) on Book.

(c) Write a new class BookByPagesComparator implements Comparator<Book>.

Level 3

A Player class implements Comparable<Player> (natural order: last name). Write a GamesPlayedDescendingComparator implements Comparator<Player> class that orders players by games played, most games first. Include all required coding-standard elements. Then explain in one sentence what would have to change in Player.java to support this ordering instead.

package cscd211Comparators;

import java.util.Comparator;
import cscd211Classes.Player;

public class GamesPlayedDescendingComparator implements Comparator<Player>
{
    @Override
    public int compare(final Player a, final Player b)
    {
        if (a == null || b == null)
            throw new IllegalArgumentException(
                "Bad Player in GamesPlayedDescendingComparator.compare");
        return Integer.compare(b.getGamesPlayed(), a.getGamesPlayed());
    }
}

Go Deeper (optional)

This section is for when you are curious, not for writing correct code on the lab. Everything you need to do the work is already above.

The Comparator<T> design has a precise mathematical meaning: a comparator instance is a binary relation that imposes a strict total order on its type. The three contract rules (antisymmetry, transitivity, totality) are exactly the axioms of a strict total order from discrete math and order theory. The reason those contract rules matter in practice is that sorting algorithms depend on them; a comparator that violates transitivity can produce an infinite loop or a garbled output from Arrays.sort.

The design pattern at work here is Strategy. The comparator object encapsulates one algorithm (comparison by team, comparison by games played) and makes it swappable at the call site. Parnas described this principle in 1972 under the heading of information hiding: each ordering decision is isolated behind its own module so that a change to one ordering cannot affect any other. The Strategy pattern is the object-oriented name for the same idea. When you later see lambdas and Comparator.comparing, you are still using Strategy; the named class is just replaced by a first-class function value, which is the functional-programming surface of the same concept.

The has-a vs. is-a distinction also applies: a type that implements Comparable says “I am an ordered thing,” while a type that implements Comparator says “I have a way to order two things of type T.” The comparator has an ordering; the comparable is an ordering. This is why a Comparator can be an object with no fields at all (its only job is to hold the comparison logic) while Comparable lives inside the type that owns the data.

In production Java code, almost every sort uses a Comparator rather than the natural order, because the sort criterion is context-specific: by date in one report, by revenue in another, by customer name for one export and by region code for another. Knowing when to reach for a Comparator rather than modifying compareTo is a routine decision in enterprise development.

Check Yourself

Close the notes and answer each one from memory, then reveal it. Pulling an idea back from memory is one of the strongest ways to make it stick.