Selection Sort: Comparisons and Swaps

A sort does two kinds of work: it compares elements, and it moves them. For every sort in this chapter, moving means swapping two elements, so let’s count comparisons and swaps separately. Here is selection sort again:

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;
      }
    }
    int temp = arr[end];
    arr[end] = arr[maxIndex];
    arr[maxIndex] = temp;
  }
}

Comparisons

The comparison is arr[j] > arr[maxIndex], and it runs once per iteration of the inner loop. The inner loop runs end times, so the passes make $n-1$ comparisons, then $n-2$, down to $1$. That is the triangular sum, $(n-1)+(n-2)+\cdots +1=\frac{n(n-1)}{2}$.

The input does not change that count. The inner loop has fixed bounds and no way to stop early, because it cannot know it has found the largest element until it has looked at every element. A sorted array, a reverse-sorted array, and a shuffled array all cost exactly $\frac{n(n-1)}{2}$ comparisons. That is $O(n^2)$, as we already knew, and now we have the exact count.

Swaps

There is exactly one swap per pass, and there are $n-1$ passes, so the code above always does $n-1$ swaps.

Some of those swaps do nothing. When the largest remaining element is already at end, maxIndex equals end and the swap exchanges the element with itself. We can skip those with one check:

if (maxIndex != end) {
  int temp = arr[end];
  arr[end] = arr[maxIndex];
  arr[maxIndex] = temp;
}

With that check in place, the number of swaps depends on the input, and the range is small. It is at most $n-1$, one per pass. It can be as low as $0$.

• An already-sorted array needs $0$ swaps. Every pass finds the largest remaining element already at end.
• A reverse-sorted array needs only about $n/2$ swaps. Take [5, 4, 3, 2, 1]. The first pass swaps 5 with 1 and gets [1, 4, 3, 2, 5]. The second swaps 4 with 2 and gets [1, 2, 3, 4, 5]. Every remaining pass finds the largest remaining element already at end. Each swap fixed two elements at once, so two passes did all the moving.
• The worst input for swaps is one where every pass has to move something, such as [2, 3, 4, 5, 1]. The first pass swaps 5 with 1, the second swaps 4 with 1, the third swaps 3 with 1, and the fourth swaps 2 with 1. That is $n-1$ swaps, and each one moves the 1 one slot to the left.

So for selection sort the reverse-sorted array is not the worst case. That is different from what we will see with bubble sort and insertion sort, where reverse-sorted is the worst input.

Time and Space Complexity

The running time is $O(n^2)$ on every input, so the best case and the worst case are the same. The swaps are at most $n-1$, which is $O(n)$, and a swap is three assignments, so selection sort does at most $3(n-1)$ assignments for its swaps. That matters when moving elements is expensive and comparing is cheap.

The auxiliary space is $O(1)$. The only extra variables are end, maxIndex, j, and temp.