Selection Sort

Overview

Selection sort works by iterating upward through an array, swapping the value in the current position with the smallest value in the remainder of the array.

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

Loop Invariant

Selection sort has loop invariant $P$ given by

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

• 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.