Selection Sort: The Code

  • Understand the implementation of selection sort.
  • Understand the use and operations of the SortingAlgorithm interface.
  • Understand the use and operation of Java's Comparable interface.

Please download the starter code for this chapter.

Here is how we have implemented selection sort:

/**
 * The basic Selection Sort algorithm.
 *
 * @param <T> Element type.
 */
public final class SelectionSort<T extends Comparable<T>>
    implements SortingAlgorithm<T> {

  // is a less than b?
  private boolean less(T a, T b) {
    return a.compareTo(b) < 0;
  }

  @Override
  public void sort(IndexedList<T> indexedList) {
    // We try to put "correct" values into a[0], a[1], ... a[n-2];
    // once a "correct" value is in a[n-2], the very last value
    // has to be the largest one anyway; thus it's also "correct".
    for (int i = 0; i < indexedList.length() - 1; i++) {
      // We're trying to put the "correct" element in a[i].
      // We need to find the smallest element in a[i..n-1].
      // We start by assuming a[i] is the smallest one.
      int min = i;
      // Now we try to find a smaller one in a[i+1..n-1].
      for (int j = i + 1; j < indexedList.length(); j++) {
        if (this.less(indexedList.get(j), indexedList.get(min))) {
          min = j;
        }
      }
      // Now we have the "true" minimum at a[min], and we
      // swap it with a[i], unless i == min of course.
      if (min != i) {
        T t = indexedList.get(i);
        indexedList.put(i, indexedList.get(min));
        indexedList.put(min, t);
      }
    }
  }

  @Override
  public String name() {
    return "Selection Sort";
  }
}
Frequently asked questions!

Q: Why SelectionSort implements SortingAlgorithm?

Answer

SortingAlgorithm is an interface we provided which encapsulates the essence of a sorting algorithm:

public interface SortingAlgorithm<T extends Comparable<T>> {
  void sort(IndexedList<T> list);
  String name();
}

Given an object of SortingAlgorithm, we can (a) ask it to sort a given IndexedList and (b) ask it for its name (e.g., "Selection Sort").

Q: Why the generic parameter T extends Comparable<T>?

Answer

Things to be sorted need an order, and we need a way to compare items, not just for equality (there's an equals() method on all objects) but for less-than and greater-than as well.

Therefore, we need a bounded type parameter. The elements to be sorted (of type T) must be Comparable. That, in turn, ensures that we have a method compareTo() that we can use to establish order.

Q: What is Comparable?

Answer

It is an interface in Java.

public interface Comparable<T> {
  /**
  * Compares this object with the specified object for order.
  *
  * @param  o the object to be compared.
  * @return a negative integer, zero, or a positive integer 
  *         as this object is less than, equal to, or greater 
  *         than the specified object.
  */
  int compareTo(T o);
}

  • Most Java built-in types implement Comparable (e.g. String, Integer, etc.)

  • We implement this interface in many classes, particularly if we want to sort a collection of their objects.

See Comparable on Oracle's website for more.

Q: Why is there a less method?

Answer

The less method encapsulates the notion of comparing two elements: "is a less than b?". It simply makes for a more readable code that is easier to update if the notion of "$<$" changes.