Sorting — Comparable & Comparator

I. Notebook Summary#

Copy-by-hand cheat sheet. Telegraphic. Lead with the term, then the rule. Everything here is derivable from Section II.

=== UNIT TESTING / JUnit ===
Unit test  = test 1 small unit (method/class) in isolation
           → catch bugs early, before integration
JUnit      = Java unit-testing framework; auto run tests fast
JUnit 5    = Platform + Jupiter + Vintage (Vintage runs JUnit 4) [+]

Annotations (Jupiter, org.junit.jupiter.api):
  @Test        → marks a test method
  @DisplayName → readable test label
  @BeforeEach  → runs before EVERY test  (fresh setup)
  @AfterEach   → after every test        (cleanup)
  @BeforeAll   → once, before all  (must be static) [+]
  @AfterAll    → once, after all   (must be static) [+]
  @ParameterizedTest → same test, many inputs
  @RepeatedTest(n)   → run test n times

Assertions (org.junit.jupiter.api.Assertions, static):
  assertEquals(exp, act)   exp FIRST [+]
  assertTrue / assertFalse condition
  assertNull / assertNotNull
  assertThrows(Ex.class, () -> code())  → returns the ex [+]
  NOTE: == checks reference; assertEquals uses .equals() [+]

=== THE PROBLEM ===
Sort List<Student> by rollNo (asc).
  naive  → write a custom sort method by hand   (don't)
  better → Comparable (natural order)
  best+  → Comparator (many orders, no class edits)

Collections.sort(list)            → needs Comparable
Collections.sort(list, cmp)       → uses a Comparator
list.sort(cmp)                     → same, since Java 8 [+]

Comparable vs Comparator — the core table#

=== compareTo / compare RETURN CONTRACT ===
return > 0  → this/first  is GREATER → comes AFTER
return < 0  → this/first  is LESS    → comes BEFORE
return = 0  → equal                  → order unchanged

ASC  trick:  this.field - other.field
DESC trick:  other.field - this.field    (flip operands)
SAFE (no overflow): Integer.compare(a, b)   [+]
doodle: number line ──(-)──0──(+)──> ; "-" = before 0, "+" = after

=== COMPARABLE — recipe ===
class Student implements Comparable<Student> {
  int rollNo;
  public int compareTo(Student o){
    return Integer.compare(this.rollNo, o.rollNo); // asc
  }
}
Collections.sort(students);     // uses compareTo
doodle: one box "Student" with a built-in ruler inside it

=== COMPARATOR — recipe ===
class AgeComparator implements Comparator<Student> {
  public int compare(Student a, Student b){
    return Integer.compare(a.age, b.age);
  }
}
Collections.sort(students, new AgeComparator());
Collections.sort(students, new RollNoComparator());
doodle: box "Student" + several external rulers (age, roll, name)

=== COMPARATOR — modern (Java 8+) [+] ===
comparing(Student::getAge)                 // asc by age
  .reversed()                              // desc
  .thenComparing(Student::getName)         // tie-break
comparingInt(Student::getRollNo)           // no boxing
nullsFirst(...) / nullsLast(...)           // null-safe
doodle: chain of links: [age]→[name]→[roll] = thenComparing

=== WHEN TO USE WHICH ===
Comparable  → you own class + ONE natural order (e.g. by id)
Comparator  → can't edit class / want MANY orders / 3rd-party type
Both can coexist: Comparator overrides natural order at call site [+]

=== TRIPLE SORTING (Codewars idea) ===
Sort by 3 attributes in priority order:
  comparingInt(a).thenComparingInt(b).thenComparing(c)
First key decides; ties fall through to next key. [+]
doodle: 3 sieves stacked; item drops to next sieve only on a tie

=== SCIENTIFIC DEBUGGING (be independent) ===
1 OBSERVE   reproduce the bug reliably
2 HYPOTHE   "I think X causes it"
3 PREDICT   "if true, then Y happens"
4 EXPERIMENT log / breakpoint / change one thing
5 CONCLUDE  confirm or reject → repeat
RULE: change ONE variable at a time. [+]
doodle: loop arrow: observe→guess→test→learn→(back to top)

II. Detailed Study Notes#

Primary learning material. Each concept: definition → intuition → why it matters → trade-offs/pitfalls → examples. + marks anything I added or corrected beyond the source.

1.Unit Testing & JUnit#

A unit test checks one small piece of code in isolation so bugs surface early, and JUnit is the framework that makes those tests easy to write and run in Java.

Unit testing validates individual units of source code — usually a single method or class — independently of everything around it. The payoff is timing: if each piece is proven correct on its own, the errors that show up when you later wire pieces together drop sharply, because you've already ruled out the small parts.

JUnit is the de-facto unit-testing framework for Java. It lets you write small test methods and run them automatically and quickly, getting a green/red result instead of eyeballing System.out.println output.

Real-world example: a payments method applyDiscount() gets a unit test feeding it $100 + 10% and asserting $90. Later someone "optimizes" the math; if they introduce a rounding bug, the test goes red before the code ever reaches production.

See it run: Code §III · JUnit example.

2.JUnit Annotations#

Annotations are tags that tell JUnit what a method is and when to run it.

• @Test — marks a method as a test. JUnit discovers and runs it.
• @DisplayName("...") — gives the test a human-readable name in reports instead of the raw method name.
• @BeforeEach — runs before each test method; use it to build fresh objects so tests don't leak state into one another.
• + @AfterEach — runs after each test (cleanup, e.g. close a file/connection).
• + @BeforeAll / @AfterAll — run once for the whole class, before/after all tests. In JUnit 5 these must be static (unless you change the test instance lifecycle).
• @ParameterizedTest — runs the same test body against many input values.
• @RepeatedTest(n) — runs a test n times (useful for flaky/timing checks).

See it run: Code §III · Lifecycle demo.

3.JUnit Assertions#

Assertions are the checks that decide pass or fail; if an assertion is false, the test fails.

All of these are static methods on Assertions (commonly import static org.junit.jupiter.api.Assertions.*;).

See it run: Code §III · Assertions demo.

4.The Sorting Problem (why we need an ordering)#

Java can sort numbers and strings out of the box, but to sort your own objects it must be told what "less than" means for them.

The driving task: given a List<Student>, sort it by roll number ascending. The naive instinct is to hand-write a sorting method (loop, compare fields, swap). That works but is the wrong layer of abstraction — you'd re-implement sorting logic the JDK already ships, and you'd repeat it for every new sort key.

The better path is to keep using the JDK's tuned sort (Collections.sort, a stable merge-sort variant) and just supply the comparison rule. Two mechanisms exist for that: Comparable (built into the class) and Comparator (supplied separately).

5.The Comparable Interface (natural ordering)#

Comparable bakes a single, default "natural" ordering directly into the class via one method, compareTo.

Comparable<T> is used to make a class's objects sortable. It declares exactly one method:

public int compareTo(T o)

It returns a positive int if this is greater than o, negative if this is less than o, and zero if they're equal. Once a class implements Comparable<Student> and overrides compareTo, calling Collections.sort(list) sorts by that rule with no extra arguments.

Recipe: (1) class Student implements Comparable<Student>, (2) override compareTo(), (3) call Collections.sort(students).

Analogy: Comparable is a built-in ruler glued inside each object. Hand the object to a sorter and it can measure itself against another of its kind. But there's only one ruler, so only one notion of order.

Best practice: keep compareTo consistent with equals — if a.compareTo(b)==0 you generally want a.equals(b) too, otherwise TreeSet/TreeMap behave surprisingly (they use compareTo, not equals). +

See it run: Code §III · Comparable.

6.The Return-Value Contract (asc, desc, tie-break)#

The sign of the returned int — not its magnitude — decides order; flip the operands to reverse it.

Picture a number line. A return value places one element relative to the other: a positive number means "I sit to the right (after) you," negative means "to the left (before)," zero means "same spot." Both compareTo and compare obey the identical contract.

7.The Comparator Interface (external, multiple orderings)#

Comparator defines an ordering outside the class, so you can have many strategies without touching — or even owning — the type.

Comparator<T> is also used to sort collection elements, but the comparison lives in a separate object. Its primary method takes two arguments:

public int compare(T a, T b)   // same +/-/0 contract
public boolean equals(Object o) // compares two comparators (rarely overridden)

compare returns positive if the first argument is greater than the second, negative if less, zero if equal. To use it, pass an instance as the second argument: Collections.sort(students, new AgeComparator()). You can define as many comparators as you have orderings — AgeComparator, RollNoComparator, NameComparator — and pick one per call.

Analogy: if Comparable is a ruler glued inside the object, Comparator is a drawer full of external measuring tools — pick "the age ruler" today, "the name ruler" tomorrow, and the Student class never changes.

See it run: Code §III · Comparator.

8.Comparable vs Comparator — side by side#

Same goal (define order), opposite placement: one inside the class for the single default, one outside for many flexible orders.

9.Modern Comparators (Java 8+ factory methods)#

Since Java 8 you rarely write a whole comparator class — you build one declaratively from method references.

Example: sort by age ascending, then name ascending for ties: list.sort(comparingInt(Student::getAge).thenComparing(Student::getName));

See it run: Code §III · Modern comparators.

10.Triple Sorting (sort by three attributes)#

Multi-key sorting is just a priority chain: the first key decides, and only ties fall through to the next key.

The practice exercise is to sort and stringify a list by three attributes at once. The clean solution chains comparators in priority order:

comparingInt(X::getA)
  .thenComparingInt(X::getB)
  .thenComparing(X::getC)

See it run: Code §III · Triple sort.

11.Becoming an Independent Developer: Scientific Debugging#

Debugging is a science: form a hypothesis, predict, test one change at a time, and let evidence (not guessing) drive the fix.

Connection: unit tests (§1–3) are the fastest "experiment" tool here — a failing test reproduces the bug on demand and a passing one confirms the fix, closing the loop quickly.

III. Code Samples#

Runnable Java (standard library only, Java 17 LTS syntax). Each block has a filename, run command, inline comments, and expected output. JUnit blocks assume JUnit 5 on the classpath.

0.Shared model: Student#

public class Student implements Comparable<Student> {  // natural order = rollNo
    private final int rollNo;
    private final String name;
    private final int age;

    public Student(int rollNo, String name, int age) {
        this.rollNo = rollNo; this.name = name; this.age = age;
    }
    public int getRollNo() { return rollNo; }
    public String getName()  { return name; }
    public int getAge()    { return age; }

    @Override                                // natural ordering: rollNo ascending
    public int compareTo(Student o) {
        return Integer.compare(this.rollNo, o.rollNo); // overflow-safe, not a-b
    }
    @Override
    public String toString() {
        return "#" + rollNo + " " + name + "(" + age + ")";
    }
}

1.JUnit basics — Notes §1#

import static org.junit.jupiter.api.Assertions.*;  // static import: assertEquals(...)
import org.junit.jupiter.api.*;

class CalcTest {
    @Test
    @DisplayName("2 + 3 = 5")              // readable label in report
    void adds() {
        int sum = 2 + 3;
        assertEquals(5, sum);            // expected FIRST, actual SECOND
    }
}

2.Lifecycle annotations — Notes §2#

import org.junit.jupiter.api.*;

class LifecycleTest {
    @BeforeAll static void all()  { System.out.println("BeforeAll (once)"); }
    @BeforeEach      void each() { System.out.println("  BeforeEach"); }
    @AfterEach       void aEach(){ System.out.println("  AfterEach"); }
    @AfterAll  static void aAll() { System.out.println("AfterAll (once)"); }

    @Test void t1() { System.out.println("    test1"); }
    @Test void t2() { System.out.println("    test2"); }
}

3.Assertions incl. assertThrows — Notes §3#

import static org.junit.jupiter.api.Assertions.*;
import org.junit.jupiter.api.*;
import java.util.*;

class AssertionsTest {
    @Test void basics() {
        assertEquals(4, 2 + 2);             // equality via .equals()
        assertTrue("hi".startsWith("h"));      // boolean condition
        assertNotNull(new Object());           // not null
    }
    @Test void throwsOnBadIndex() {
        List<Integer> xs = List.of(1, 2);
        // assertThrows RETURNS the exception so we can inspect it
        Exception e = assertThrows(IndexOutOfBoundsException.class,() -> xs.get(5));            // the code expected to throw
        assertNotNull(e.getMessage());
    }
}

4.Comparable — natural order — Notes §5#

import java.util.*;

public class ComparableDemo {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>(List.of(new Student(3, "Asha", 21), new Student(1, "Ravi", 23), new Student(2, "Meera", 20)));

        Collections.sort(students);   // uses Student.compareTo -> rollNo asc
        System.out.println(students);
    }
}

5.Comparator — multiple orders — Notes §7#

import java.util.*;

// External ordering #1: by age ascending
class AgeComparator implements Comparator<Student> {
    @Override public int compare(Student a, Student b) {
        return Integer.compare(a.getAge(), b.getAge());
    }
}
// External ordering #2: by rollNo DESCENDING (operands flipped)
class RollNoDescComparator implements Comparator<Student> {
    @Override public int compare(Student a, Student b) {
        return Integer.compare(b.getRollNo(), a.getRollNo()); // b,a = desc
    }
}

public class ComparatorDemo {
    public static void main(String[] args) {
        List<Student> s = new ArrayList<>(List.of(new Student(3, "Asha", 21), new Student(1, "Ravi", 23), new Student(2, "Meera", 20)));

        Collections.sort(s, new AgeComparator());        // pass the strategy
        System.out.println("by age  : " + s);
        Collections.sort(s, new RollNoDescComparator());
        System.out.println("roll desc: " + s);
    }
}

6.Modern comparators (Java 8+) — Notes §9#

import java.util.*;
import static java.util.Comparator.*;   // comparing, comparingInt, ...

public class ModernComparatorDemo {
    public static void main(String[] args) {
        List<Student> s = new ArrayList<>(List.of(new Student(3, "Asha", 21), new Student(1, "Ravi", 21), new Student(2, "Meera", 20)));

        // age asc, then name asc on ties; .sort is a List method
        s.sort(comparingInt(Student::getAge).thenComparing(Student::getName));
        System.out.println(s);

        s.sort(comparing(Student::getName).reversed()); // name desc
        System.out.println(s);
    }
}

7.Triple sorting — Notes §10 #

import java.util.*;
import static java.util.Comparator.*;

public class TripleSortDemo {
    public static void main(String[] args) {
        List<Student> s = new ArrayList<>(List.of(new Student(5, "Asha", 21), new Student(2, "Asha", 21), new Student(9, "Asha", 19), new Student(1, "Bina", 19)));

        // priority: age asc -> name asc -> rollNo asc
        s.sort(comparingInt(Student::getAge).thenComparing(Student::getName).thenComparingInt(Student::getRollNo));
        s.forEach(System.out::println);
    }
}

8.Unit-testing a sort (ties it all together)#

import static org.junit.jupiter.api.Assertions.*;
import org.junit.jupiter.api.*;
import java.util.*;

class SortTest {
    private List<Student> students;

    @BeforeEach void setUp() {        // fresh list per test
        students = new ArrayList<>(List.of(new Student(3, "Asha", 21), new Student(1, "Ravi", 23)));
    }
    @Test @DisplayName("natural order sorts by rollNo asc")
    void naturalOrder() {
        Collections.sort(students);
        assertEquals(1, students.get(0).getRollNo());
        assertEquals(3, students.get(1).getRollNo());
    }
}

IV. Hands-On Lab#

Build it yourself. Predict before you run. Solutions are collapsed — open only after attempting.

// see Code §0 (Student) and §4 (ComparableDemo)
@Override public int compareTo(Student o) {
    return Integer.compare(this.rollNo, o.rollNo); // asc
}

Collections.sort(list, Collections.reverseOrder()); // reverses NATURAL order
// equivalent modern form:
list.sort(Comparator.<Student>naturalOrder().reversed());

class AgeComparator implements Comparator<Student> {
    @Override public int compare(Student a, Student b) {
        return Integer.compare(a.getAge(), b.getAge());
    }
}

import static java.util.Comparator.*;
list.sort(comparingInt(Student::getAge)); // no boxing

import static java.util.Comparator.*;
list.sort(comparingInt(Student::getAge)
        .thenComparing(Student::getName)
        .thenComparingInt(Student::getRollNo));

import static org.junit.jupiter.api.Assertions.*;
import org.junit.jupiter.api.*;
import java.util.*;

class SortChallengeTest {
    List<Student> xs;
    @BeforeEach void init() {
        xs = new ArrayList<>(List.of(new Student(3,"A",21), new Student(1,"B",22)));
    }
    @Test void sortsAsc() {
        Collections.sort(xs);
        assertEquals(1, xs.get(0).getRollNo());
        assertEquals(3, xs.get(1).getRollNo());
    }
    @Test void immutableThrows() {
        List<Student> fixed = List.of(new Student(2,"C",20), new Student(1,"D",19));
        assertThrows(UnsupportedOperationException.class,() -> Collections.sort(fixed));
    }
}

Key Takeaways#

• Don't hand-write sorting — supply a comparison rule and let Collections.sort/list.sort (stable) do the work.
• Comparable = one natural order, lives inside the class, compareTo(o), sort(list).
• Comparator = many orders, lives outside the class, compare(a,b), sort(list, cmp) — and it's the only option for types you can't modify.
• The contract is sign-only: +after, −before, 0 equal. Flip operands for descending. Use Integer.compare to dodge overflow.
• Multi-key sorting is a priority chain via thenComparing; ties fall through key by key, and stability holds equal elements in place.
• JUnit proves it: @Test/@BeforeEach + assertEquals/assertThrows turn "I think it sorts right" into "it's verified, and stays verified."
• Independence = scientific debugging: reproduce, hypothesize, predict, change one thing, conclude — with a failing test as your fastest experiment.