Selection Sort

Overview

Property	Value
Best Case	$\Omega (n^2)$
Worst Case	$O(n^2)$
Avg. Case	$O(n^2)$
Aux. Memory	$O(1)$
Stable	No
Adaptive	No

void swap(int i, int j, int *A) {
  int tmp = A[i];
  A[i] = A[j];
  A[j] = tmp;
}
 
void selection_sort(const int n, int A[static n]) {
  for (int i = 0; i < n - 1; ++i) {
	int mini = i;
    for (int j = i + 1; j < n; ++j) {
      if (A[j] < A[mini]) {
	    mini = j;
      }
    }
    swap(i, mini, A);
  }
}

Loop Invariant

Consider loop invariant $P$ given by

A[0:i-1] is a sorted array of the i least elements of A.

We prove $P$ maintains the requisite properties:

• Initialization
  • When i = 0, A[0:-1] is an empty array. This trivially satisfies $P$.
• Maintenance
  • Suppose $P$ holds for some 0 ≤ i < n - 1. Then A[0:i-1] is a sorted array of the i least elements of A. Our inner loop then finds the smallest element in A[i:n] and swaps it with A[i]. Therefore A[0:i] is a sorted array of the i + 1 least elements of A. At the end of the iteration, i is incremented meaning A[0:i-1] still satisfies $P$.
• Termination
  • On termination, i = n - 1 and A[0:n-2] are the n - 1 least elements of A in sorted order. But, by exhaustion, A[n-1] must be the largest element meaning A[0:n-1], the entire array, is in sorted order.

Bibliography

• Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).