Sorting Objects
Collections.sort, Arrays.sort, and natural ordering
Reading: Reges & Stepp: Ch. 10
After this lesson, you will be able to:
- Sort arrays of objects using
Arrays.sort()withComparable - Sort
ArrayListobjects usingCollections.sort() - Implement selection sort on object arrays using
compareTo - Sort by multiple fields with tiebreakers
- Explain the difference between stable and unstable sorts
- Use
Comparatorfor alternate sort orders
You Already Know How to Sort
In Lesson 2.3, you wrote selection sort for int[]. You compared elements with <. That worked because integers have a built-in ordering: 3 is less than 7, always.
But what about Student objects? Is Alice less than Bob? By name? By GPA? By ID? There is no built-in < for objects. The compiler has no idea how to rank your custom classes.
That is exactly the problem Comparable solves. In the previous lesson, you wrote compareTo to define a natural ordering for your objects. Now you get to use it. Once a class implements Comparable<T>, Java’s sorting methods work on it automatically.
From CSCD 110: In Python, you could sort a list of objects with
sorted(students, key=lambda s: s.gpa). The lambda told Python how to extract a sort key. Java’sComparableinterface serves the same purpose, but the comparison logic lives inside the class itself, not at the call site.
Sorting with Arrays.sort()
Here is a Student class that implements Comparable<Student>, sorting by GPA (descending), then by name (ascending) as a tiebreaker:
import java.util.Arrays;
public class Student implements Comparable<Student> {
private final String name;
private final double gpa;
private final int id;
public Student(final String name, final double gpa, final int id) {
this.name = name;
this.gpa = gpa;
this.id = id;
}
public String getName() {
return this.name;
}
public double getGpa() {
return this.gpa;
}
public int getId() {
return this.id;
}
@Override
public int compareTo(final Student other) {
// Primary: GPA descending (flip arguments for descending)
int gpaResult = Double.compare(other.gpa, this.gpa);
if (gpaResult != 0) {
return gpaResult;
}
// Tiebreaker: name ascending
return this.name.compareTo(other.name);
}
@Override
public String toString() {
return this.name + " (ID: " + this.id + ", GPA: " + this.gpa + ")";
}
}
Now sorting an array is one line:
public class Main {
public static void main(final String[] args) {
Student[] roster = {
new Student("Zoe", 3.5, 1005),
new Student("Alice", 3.8, 1001),
new Student("Bob", 3.8, 1002),
new Student("Charlie", 3.2, 1003)
};
System.out.println("Before sort:");
for (final Student s : roster) {
System.out.println(" " + s);
}
Arrays.sort(roster); // Uses compareTo internally
System.out.println("\nAfter sort:");
for (final Student s : roster) {
System.out.println(" " + s);
}
}
}
Output:
Before sort:
Zoe (ID: 1005, GPA: 3.5)
Alice (ID: 1001, GPA: 3.8)
Bob (ID: 1002, GPA: 3.8)
Charlie (ID: 1003, GPA: 3.2)
After sort:
Alice (ID: 1001, GPA: 3.8)
Bob (ID: 1002, GPA: 3.8)
Zoe (ID: 1005, GPA: 3.5)
Charlie (ID: 1003, GPA: 3.2)
Alice and Bob both have 3.8 GPA, so the tiebreaker kicks in: “Alice” comes before “Bob” alphabetically. Zoe (3.5) comes next, then Charlie (3.2). Highest GPA first.
Key Insight:
Arrays.sort()does not know anything about students, GPAs, or names. It callscompareTorepeatedly and uses the return values (negative, zero, positive) to decide the order. YourcompareTomethod is the single source of truth for ordering.
Sorting with Collections.sort()
Arrays.sort() works on arrays. For ArrayList, use Collections.sort():
import java.util.ArrayList;
import java.util.Collections;
public class RosterDemo {
public static void main(final String[] args) {
ArrayList<Student> roster = new ArrayList<>();
roster.add(new Student("Zoe", 3.5, 1005));
roster.add(new Student("Alice", 3.8, 1001));
roster.add(new Student("Bob", 3.8, 1002));
roster.add(new Student("Charlie", 3.2, 1003));
Collections.sort(roster); // Uses compareTo internally
for (final Student s : roster) {
System.out.println(s);
}
}
}
The output is identical. Both methods rely on the same compareTo method.
| Method | Works on | Import |
|---|---|---|
Arrays.sort(arr) |
Arrays (T[]) |
java.util.Arrays |
Collections.sort(list) |
Lists (ArrayList<T>, etc.) |
java.util.Collections |
Both require that the element type implements Comparable<T>. If it does not, the code will not compile.
Check Your Understanding
You have an
---
## How Sorting Algorithms Use `compareTo`
Behind the scenes, `Arrays.sort()` uses a sophisticated algorithm (a variant of mergesort for objects). But the principle is the same as the selection sort you wrote in Lesson 2.3. The only change: instead of comparing primitives with `<`, the algorithm calls `compareTo`.
Here is selection sort adapted for objects. Compare this to the `int[]` version you already know:
```
Sorting int[]: Sorting Comparable[]:
───────────── ────────────────────
if (arr[j] < arr[minIndex]) if (arr[j].compareTo(arr[minIndex]) < 0)
```
That is it. The algorithm structure is identical. Only the comparison changes.
### Selection Sort on Objects: Complete Implementation
```java
public class ObjectSorter {
/**
* Sorts an array of Comparable objects using selection sort.
* @param arr the array to sort
*/
public static <T extends ComparableArrayList<Student> where Student implements Comparable<Student>. Which call sorts it?</p>
Arrays.sort() works on arrays, not ArrayList. Collections.sort() is the correct method for sorting ArrayList and other List types. Option C would work with a Comparator argument, but without one it does not compile.
Check Your Understanding
In the selection sort for objects, what replaces the primitive comparison
---
## Sorting by Different Fields
Your `compareTo` method defines one natural ordering. But what if you need different orderings in different parts of your program?
### Scenario 1: Sort by One Field
```java
@Override
public int compareTo(final Student other) {
return this.name.compareTo(other.name); // Alphabetical by name
}
```
### Scenario 2: Multiple Fields with Tiebreakers
```java
@Override
public int compareTo(final Student other) {
int gpaResult = Double.compare(other.gpa, this.gpa); // GPA descending
if (gpaResult != 0) {
return gpaResult;
}
return this.name.compareTo(other.name); // Name ascending as tiebreaker
}
```
### Scenario 3: Descending Order
> **The Trick:** To reverse the sort order, flip the arguments to the comparison. Instead of `Double.compare(this.gpa, other.gpa)` (ascending), write `Double.compare(other.gpa, this.gpa)` (descending). Do not negate the result — negating `Integer.MIN_VALUE` overflows.
---
## Stable vs. Unstable Sorts
A **stable** sort preserves the relative order of equal elements. An **unstable** sort does not guarantee this.
Suppose you sort students by GPA and two students both have 3.8:
```
Before sort: [Zoe 3.8, Alice 3.8, Bob 3.2]
Stable sort: [Zoe 3.8, Alice 3.8, Bob 3.2] ← Zoe still before Alice
Unstable sort: [Alice 3.8, Zoe 3.8, Bob 3.2] ← Order may change
```
In Java, `Arrays.sort()` for objects uses a **stable** mergesort. `Arrays.sort()` for primitives uses a **unstable** dual-pivot quicksort. `Collections.sort()` is always stable.
This matters when you sort by multiple criteria in stages: sort by name first, then stable-sort by GPA, and the name order is preserved within each GPA group.
---
## Comparator: An Alternative Ordering
`Comparable` defines the **natural** ordering inside the class. But sometimes you need a different ordering without changing the class. Java provides `Comparator` for this.
```java
import java.util.Arrays;
import java.util.Comparator;
public class SortByName {
public static void main(final String[] args) {
Student[] roster = {
new Student("Zoe", 3.5, 1005),
new Student("Alice", 3.8, 1001),
new Student("Bob", 3.2, 1002)
};
// Sort by name (ascending), ignoring the natural GPA ordering
Arrays.sort(roster, new Comparatorarr[j] < arr[minIndex]?</p>
The
< operator does not work on objects. You call compareTo, which returns a negative integer when the receiver is "less than" the argument. So arr[j].compareTo(arr[minIndex]) < 0 means "arr[j] comes before arr[minIndex]." Option D checks for equality, not less-than.
Check Your Understanding
A
---
## Complete Example: The Roster Pipeline
Here is a complete program that creates students, sorts them, and prints a report. This is the pattern you will use in labs: create, sort, process.
```java
import java.util.ArrayList;
import java.util.Collections;
public class RosterReport {
public static void main(final String[] args) {
// 1. Build the roster
ArrayListStudent class sorts by GPA descending via compareTo. You need to sort a Student[] by name instead, without changing the Student class. What do you use?</p>
A
Comparator defines an external comparison strategy. Pass it as the second argument to Arrays.sort(roster, comparator) to override the natural ordering without modifying the class. Option A would work but is unnecessarily complex. Options C and D would not compile for this purpose.