Comparing Objects in Java

Selection sort repeatedly finds the smallest remaining item in the unsorted region and places it at the boundary, so the sorted region grows by one position per pass.

Programming

Why Sorting Needs a Rule

Suppose you have a list of numbers and want them in increasing order. You can probably do this by eye, because numbers have an obvious order. Strings also have an order that a program can use. Now suppose the list holds objects you wrote yourself, such as employees, addresses, or playing cards. A program cannot sort those until it knows how to decide that one object comes before another. For custom objects there is no built-in notion of that criterion, so something must be defined for comparing them first.

Definition

Sorting means arranging items in ascending order according to some criterion. The criterion is the comparison. Without a defined comparison, the phrase in ascending order has no meaning for those objects.

This article follows one question through the whole topic. First you will watch a sorting algorithm, selection sort, move items one pass at a time. Then you will see how the comparison rule decides where each item lands. Finally you will see how Java lets a class carry its own comparison rule, or lets a separate object supply one. Each step asks you to predict something before you read the answer.

Tracing Selection Sort Pass by Pass

Selection sort is easiest to picture as two regions. The front region holds values already in their final positions. The back region, sometimes called the unsorted part, holds everything not yet placed. Each pass looks only at the back region, finds its smallest value, and moves that value to the first position of the back region. That position then becomes part of the front region, so the boundary between the regions moves one step to the right. When the back region has only one item left, the whole list is in order.

Take the list [5, 2, 8, 1] as a worked trace. The example list is generated for this article so that every step is visible. Before you read the trace, predict the list after the first pass.

What do you think happens?

Starting from [5, 2, 8, 1], what does the list look like after the first pass of selection sort?

[1, 2, 8, 5]
[1, 5, 2, 8]
[2, 5, 8, 1]
[5, 2, 8, 1]

Reveal answer

Answer:

[1, 2, 8, 5]

The back region is the whole list, so the smallest value is 1 at index 3. That 1 moves to index 0, and the 5 takes the position 1 vacated. The 2 and the 8 do not move at all, which means the first pass settles only the front position.

After each pass, what does the list look like, and which item was just moved into place?

Pass 2 looks at the back region [2, 8, 5]. Its smallest value is 2, which already sits at the first position of that region. The search finds it, the placement step has nothing to move, and the list does not change. The boundary now sits after index 1. Pass 3 looks at [8, 5]. The smallest value is 5 at index 3, so 5 moves to index 2 and the 8 moves to index 3, giving [1, 2, 5, 8]. Only one item remains in the back region after that, so the list is in order.

Worked example

Tracing the list [5, 2, 8, 1] to completion

Sort [5, 2, 8, 1] into increasing order with selection sort, showing the sorted and unsorted regions after each pass.

1
Start
The sorted region is empty. The unsorted region is the whole list [5, 2, 8, 1].
2
Pass 1
The smallest unsorted value is 1 at index 3. It is placed at index 0, and the 5 takes index 3. Result: [1, 2, 8, 5]. Sorted region: index 0.
3
Pass 2
The unsorted region is [2, 8, 5]. Its smallest value is 2, already at index 1, so nothing moves. Result: [1, 2, 8, 5]. Sorted region: indices 0 to 1.
4
Pass 3
The unsorted region is [8, 5]. Its smallest value is 5 at index 3, placed at index 2, so the 8 moves to index 3. Result: [1, 2, 5, 8]. Sorted region: indices 0 to 2.
5
Finish
Only one unsorted item (8) remains, and it is already in its final position. The list is [1, 2, 5, 8].

Result

The sorted list is [1, 2, 5, 8], reached after three passes that each placed one value at the boundary.

Locating the First Divergence

When a finished list is wrong, do not start by rereading the whole algorithm. Trace the list pass by pass and check the boundary after each one. The first pass that produces a value you did not expect marks the place where your mental picture and the real behavior disagree. The mistake is almost always in that pass's search step, which records an index, or its placement step, which uses that index. Errors in either one produce a list that is wrong in a specific, traceable place.

Where does the boundary between the sorted and unsorted regions sit after the first pass, and which cells are already final?

The diagram shows the state after the first pass. Only index 0 is in its final position, so the boundary sits after it. The 5 changed cells because it was displaced from index 0 to index 3. The 2 and the 8 did not change, but they still belong to the unsorted region and will be examined again on later passes. Each pass moves the boundary one position to the right, and the boundary is what tells you how far the algorithm has progressed.

Card Sorting With a Second List

The source applies the same idea to a hand of playing cards. Each Card object offers getSuit() and getValue() methods, and the hand is stored in an ArrayList of Card. The method described in the source does not swap cards inside the original list. Instead, it creates a second list, repeatedly selects the smallest remaining card from the old list, removes that card from the old list, and adds it to the new list. When the old list is empty, the new list becomes the hand.

The comparison rule is the part that most often confuses readers. Cards of the same suit are grouped together, and within a suit they are ordered by value. The rule is a two-key comparison. Suit is checked first. A card c1 replaces the current minimum c when its suit is smaller, or when its suit is equal and its value is smaller. Value is used only as a tie-breaker when suits match. The source also treats aces as the lowest value, 1.

The source notes that this approach is not the most efficient sorting method. It is acceptable here because a hand of cards is small, so the inefficiency is negligible. The method also shows the same search-then-place structure as the array version: find the smallest remaining item, then put it in its final place.

Comparable and the compareTo Contract

The Comparable interface is a parameterized interface, written Comparable<T>, that expresses the ability to be compared to an object of type T. It defines exactly one method, compareTo, which takes an object of type T as its parameter. Calling obj1.compareTo(obj2) asks obj1 to report where it stands relative to obj2. A class that implements Comparable<T> gives its objects a natural order, which is the order the class itself defines.

Definition

Zero from compareTo does not by itself imply equals is true, though classes should aim to keep equals and compareTo consistent.

Only the sign of the result of compareTo matters. A negative result means the receiver comes before the other object. A positive result means it comes after. Zero means the two count as the same for this comparison. The size of the number is not meaningful, so a result of -1 and a result of -40 are both negative and both mean before.

Return value	Meaning for obj1.compareTo(obj2)	Position in sorted order
Negative	obj1 is less than obj2 under the class's rule	obj1 comes before obj2
Zero	obj1 and obj2 are equal for this comparison	Neither is required to come first
Positive	obj1 is greater than obj2 under the class's rule	obj1 comes after obj2

Interpreting the sign of a compareTo result

The source develops a class called FullName, which holds a first name and a last name, both required to be non-null. To make FullName objects sortable, the class implements Comparable<FullName>. Its compareTo makes the last name the primary key, and the first name decides the order only when the last names match. The code below follows that description. It is generated for this article, and the source describes the same logic in prose.

Code walkthrough

import java.util.Objects;

public class FullName implements Comparable<FullName> {
    private final String firstName;
    private final String lastName;

    public FullName(String firstName, String lastName) {
        this.firstName = Objects.requireNonNull(firstName);
        this.lastName = Objects.requireNonNull(lastName);
    }

    public String getFirstName() { return firstName; }
    public String getLastName() { return lastName; }

    @Override
    public int compareTo(FullName other) {
        int lastCmp = this.lastName.compareTo(other.lastName);
        if (lastCmp != 0) {
            return lastCmp < 0 ? -1 : 1;
        }
        return this.firstName.compareTo(other.firstName);
    }
}

1
The class declares that it implements Comparable<FullName>, so its objects can be compared with one another.
2
The constructor rejects null names, as the source requires.
3
compareTo first compares the last names using the String comparison.
4
If the last names differ, the method returns -1 or 1 according to the sign of that comparison.
5
If the last names match, the method returns the result of comparing first names, which decides the order as a tie-breaker.

implements Comparable<FullName> declares the natural order
requireNonNull enforces that both names are non-null
The last name is compared first and is the primary key
The first name is used only when the last names are equal

What do you think happens?

Given FullName a = new FullName("Ada", "Lovelace") and b = new FullName("Charles", "Babbage"), what is the sign of a.compareTo(b)?

Negative, so a comes before b
Zero, because both are famous mathematicians
Positive, so a comes after b

Reveal answer

Answer:

Positive, so a comes after b

The last names differ, and Lovelace comes after Babbage alphabetically. The method returns 1, so a comes after b. The first names are never consulted because the last names already decided the order.

A complete class should also keep equals consistent with compareTo. The FullName example compares both names in equals, and compareTo compares last names and then first names, so the two notions agree. The code above omits equals for brevity, which means it is not yet a complete implementation.

Comparator as an Outside Rule

Comparable puts the comparison inside the class. A Comparator takes a different approach. It is a separate object whose job is to compare two objects of some type T. The object must implement Comparator<T>, and the interface defines one method, compare(T obj1, T obj2). Its return value follows the same sign convention as compareTo: negative means obj1 comes before obj2, positive means obj1 comes after obj2, and zero means the two count as the same for this comparison.

Where does each comparison logic live relative to the class being sorted, and which one does the sort call use?

The source names two situations where a Comparator is useful. The first is comparing objects whose class does not implement Comparable, such as a class you cannot modify. The second is defining several different orderings over the same collection of objects. Because Comparator is a functional interface, comparators are often written as lambda expressions. The following example sorts addresses by zip code. The Address class and the sort call are generated for illustration.

java

Comparator<Address> byZip = (a, b) -> a.getZip().compareTo(b.getZip());
Collections.sort(addresses, byZip);

Comparator<Address> byZip = (a, b) -> a.getZip().compareTo(b.getZip());
Collections.sort(addresses, byZip);

Notes on the code

The lambda implements compare(obj1, obj2) for Address
The comparator lives outside the Address class
Collections.sort receives the comparator as its second argument

Mistakes Beginners Make With Comparison

Common mistake
Assuming one pass sorts the whole list
What it looks like
After pass 1 of [5, 2, 8, 1], a learner expects [1, 2, 5, 8].
Why it fails
Each pass places only one value at the boundary. The front region grows by one position per pass, so several passes are needed.
Do this instead
Trace the boundary after each pass and count how many positions are final.
Common mistake
Reading the magnitude of a compareTo result as meaningful
What it looks like
Expecting a result of -40 to mean obj1 is forty units smaller than obj2.
Why it fails
Only the sign of the result carries the ordering decision.
Do this instead
Read negative as before, zero as equal for this comparison, and positive as after.
Common mistake
Assuming zero from compareTo means the objects are equal
Why it fails
Zero means the two count as the same for this comparison. The source notes that zero does not by itself imply equals is true.
Do this instead
Keep equals and compareTo consistent in classes that implement Comparable, and remember that a comparator may deliberately return zero for unequal objects.
Common mistake
Comparing value before suit in the card rule
What it looks like
Ordering cards by value across all suits.
Why it fails
The source's rule checks suit first and uses value only as a tie-breaker.
Do this instead
Compare suit first, and only when suits are equal compare value.
Common mistake
Sorting custom objects without defining how to compare them, because the sort routine has no rule for deciding which object comes first.
Common mistake
Expecting a Comparator to agree with equals
Why it fails
The source notes a comparator may report zero for objects that are not equal in every field, and this is an intentional ordering choice.
Do this instead
Judge a comparator by the ordering it defines, not by whether it matches equals.

Choosing Between Comparable and Comparator

Aspect	Comparable<T>	Comparator<T>
Where the logic lives	Inside the class, in compareTo	In a separate object, in compare
Method signature	compareTo(T other)	compare(T obj1, T obj2)
Number of orderings	One natural order per class	Any number of orderings over the same objects
Works without changing the class	No, the class must implement it	Yes, useful for classes you cannot modify
Typical use	Objects with an obvious default order, such as FullName by last name	Alternative orders, such as addresses by zip code

Choosing the right comparison mechanism

When a sort gives an unexpected order, locate the step where the order comes from. Ask which comparison the sort used. If no comparator was passed, the sort used the class's compareTo. If a comparator was passed, the sort used its compare method. Then trace one or two comparisons by hand to see which key decided each result.

MEDIUM

Start with the list [7, 3, 9, 1]. Trace selection sort by hand. Write the list after pass 1, after pass 2, and after pass 3. Then state which value is in its final position after each pass. Only after you have written your predictions, check them against the trace method above.

Hints

In pass 1, the back region is the whole list, so find the smallest value and place it at index 0.
In pass 2, the back region starts at index 1. Ignore index 0 because it is already final.
Pass 3 leaves two items in the back region. Compare them and place the smaller first.

Your attempt (not saved)

EASY

A FullName class compares last names first and first names second. Predict the sign of new FullName("Grace", "Hopper").compareTo(new FullName("Alan", "Turing")), then predict what would change if the first names were compared before the last names.