Selection Sort

Algorithm

Selection Sort repeatedly finds the minimum element of the unsorted suffix and swaps it with the first unsorted position. For 0-indexed arrays:

For $i = 0$ to $n-2$:

1. Find the index $j$ of the minimum element in $A[i \dots n-1]$.
2. Swap $A[i]$ with $A[j]$.

Invariant

At the start of iteration $i$, the subarray $A[0 \dots i-1]$ contains the $i$ smallest elements of the original array, in sorted order. The remaining elements $A[i \dots n-1]$ are unsorted.

• Initialisation ($i=0$): $A[0 \dots -1]$ is empty, trivially sorted.
• Maintenance: Appending the next minimum extends the sorted prefix correctly.
• Termination ($i=n-1$): $A[0 \dots n-2]$ sorted plus the final element (the largest) at $n-1$ completes the sort.

Complexity: Always $\Theta(n^2)$ Comparisons

Selection Sort performs no early exit. For each $i$, finding the minimum in the remaining $n-i$ elements requires $n-i-1$ comparisons:

$\sum_{i=0}^{n-2} (n-i-1) = \sum_{k=1}^{n-1} k = \frac{n(n-1)}{2} = \Theta(n^2)$

There is no best-case scenario that reduces comparisons; even if the array is already sorted, every element is still compared. The running time is always $\Theta(n^2)$ comparisons, making it data-insensitive.

Swaps: Only $\Theta(n)$

Each iteration performs exactly one swap, and there are $n-1$ iterations (the last element is automatically in place). Thus the total number of swaps is:

$\text{Swaps} = n-1 = \Theta(n)$

A lower bound theorem shows that any sorting algorithm must perform $\Omega(n)$ swaps in the worst case (consider the input $[2, 3, \ldots, n, 1]$ where every item starts in the wrong place, and each swap touches two items). Selection Sort achieves this lower bound exactly.

Properties

Property	Value
Comparisons	Always $\Theta(n^2)$
Swaps	$\Theta(n)$ (optimal)
In-place	Yes, $O(1)$ space
Stable	No — the swap can jump over equal elements
Data-sensitive	No — same work regardless of input

Why Stability Fails

Consider $[5_a, 5_b, 2]$. Selection Sort finds 2 as the minimum and swaps it with $5_a$, producing $[2, 5_b, 5_a]$. The relative order of $5_a$ and $5_b$ is reversed, so the sort is not stable.

When to Use

Selection Sort is effective when writes are expensive but comparisons are cheap. Each element is written at most twice (once when swapped into the sorted region, once when displaced from the unsorted region), giving $\Theta(n)$ writes total. This is optimal for sorting algorithms.

Summary

Aspect	Detail
Strategy	Repeatedly select minimum, swap to front
Comparisons	$\Theta(n^2)$, always
Swaps	$\Theta(n)$, optimal
In-place	Yes
Stable	No
Use case	Expensive writes, cheap comparisons
Lower bound achieved	$\Omega(n)$ swaps