Sorting with a Comparator

We have a GpaComparator. That is an ordering held in an object. Now let’s write a version of selectionSort that takes one, instead of assuming the natural order.

We keep the version we already have, and add a second one that accepts a Comparator and compares with compare rather than compareTo:

public static <T> int indexOfMin(DynamicArray<T> a, int from, Comparator<T> cmp) {
  int minIndex = from;
  for (int i = from + 1; i < a.size(); i++) {
    if (cmp.compare(a.get(i), a.get(minIndex)) < 0) {
      minIndex = i;
    }
  }
  return minIndex;
}

public static <T> void selectionSort(DynamicArray<T> a, Comparator<T> cmp) {
  for (int i = 0; i < a.size() - 1; i++) {
    int min = indexOfMin(a, i, cmp);
    swap(a, i, min);
  }
}

Notice that we did not rename anything. These new methods reuse the names indexOfMin and selectionSort from the previous sections, and take an extra Comparator parameter. So ArrayUtils now has two methods named selectionSort, one taking (a) and one taking (a, cmp), and two named indexOfMin, all in the same class.

That is legal Java. It is called method overloading. Several methods in a class may share a name, as long as their parameter lists differ. When you call one, Java looks at the arguments you passed and picks the method whose parameters they fit. So selectionSort(roster) calls the natural-order version, and selectionSort(roster, new GpaComparator()) calls the new one.

No Comparable bound

Look at the type parameter. It is just <T>, with no extends Comparable<T>. The natural-order version needed that bound because it called compareTo on the elements, and only a Comparable type has a compareTo. This version never calls compareTo. It calls cmp.compare, and cmp is a Comparator<T>, and the Comparator interface declares compare. Nothing in the body requires anything of T itself, so we put no bound on T. This is the same rule we followed with swap: add a bound only where the body needs it.

So this selectionSort works for any type at all, including a type that does not implement Comparable. The order comes entirely from the comparator we pass in.

Using it:

ArrayUtils.selectionSort(roster, new GpaComparator());  // roster ordered by GPA

The natural order of the roster is by ID. Here it comes out ordered by GPA, and we did not change the Student class at all.

Comparable or Comparator?

We now have two ways to define order, and they are used in different situations:

• Comparable — the type’s one natural order, built into the type. Use it when there is a single obvious ordering, like a student’s ID.
• Comparator — any order, written outside the type and chosen at the call site. Use it when you want an alternative ordering (by GPA, by name), when you need several different orderings, or when the type does not implement Comparable at all and you cannot change it.

You normally want both. Comparable gives the type a default order. A Comparator lets a caller ask for a different order without editing the type.