Selection Sort, Again

We already know one sorting algorithm. We wrote selection sort when we built the dynamic array, as a utility method over DynamicArray, and traced it there. Then, when we learned Big-Oh, we analyzed it: the inner scan is $O(n)$, it runs about $n$ times, and the triangular sum $\frac{n(n-1)}{2}$ makes the whole sort $O(n^2)$. We will not repeat any of that here.

Two things are new in this chapter. First, every sort here works on a plain int[], so we write selection sort again in that form. Second, we count more carefully than Big-Oh does. All three sorts in this chapter are $O(n^2)$, so Big-Oh cannot tell them apart. Counting comparisons and swaps can tell them apart.

To make the rewrite a little different, let’s select the largest remaining element instead of the smallest, and place it at the end instead of the front. The sorted portion then grows from the right:

public static void selectionSort(int[] arr) {
  for (int end = arr.length - 1; end > 0; end--) {
    int maxIndex = 0;
    for (int j = 1; j <= end; j++) {
      if (arr[j] > arr[maxIndex]) {
        maxIndex = j;  // found a larger element
      }
    }
    // swap the largest remaining element into position end
    int temp = arr[end];
    arr[end] = arr[maxIndex];
    arr[maxIndex] = temp;
  }
}

end is the last unsorted position. The inner loop scans arr[0] through arr[end] for the largest value, and the swap puts it at end. Then end moves one to the left. The loop stops when end reaches 0. At that point only one element is unsorted. Every larger value is already in place to its right, so it is the smallest value in the array, and it is already at index 0.

This loop keeps a loop invariant, a statement that is true every time the loop finishes an iteration: after pass i, the last i slots hold the i largest values of the array, each in its final position. The inner loop never looks at them again.

Selecting the largest rather than the smallest does not change the cost.