Ordering Elements: Comparable

Finding a student works now. Let’s try to sort the roster.

When we wrote selectionSort, we put the work of finding the smallest remaining element in indexOfMin. The comparison inside indexOfMin was this:

if (a.get(i) < a.get(minIndex)) { ... }

That < was fine for int. If you try it on a roster of Students, the line does not compile. student1 < student2 means nothing to Java. Which of two students is smaller? The one with the smaller ID? The one whose name comes first? The one with the lower GPA? Java does not define an answer to that.

In Java, <, >, and the other comparison operators work only on primitive numbers. For objects, Java has no built-in notion of order. So if we want to sort students, the Student type itself has to say how its values are ordered.

The Comparable interface

Java has an interface called Comparable for types that know how to order themselves.

I assume you have seen interfaces before, but let’s briefly review. An interface is a contract: a list of methods a type promises to provide. It says nothing about how the methods work, only that they exist. A type that implements the interface must supply those methods. And any code that needs those methods can count on them being there, without caring which particular type it is dealing with.

Comparable<T> is a one-method contract:

public interface Comparable<T> {
  int compareTo(T other);
}

A type that implements Comparable provides a method that takes another value of the same type and reports how this value compares to it. The return value of compareTo follows a fixed convention:

  • negative if this comes before other,
  • zero if the two are considered equal in order,
  • positive if this comes after other.

That is the same information <, ==, and > give us for numbers. Here it comes from a single method, and any type can implement that method.

In the next section we have Student implement Comparable and define its ordering, so we can sort our roster.