Selection sort repeatedly finds the minimum of the unsorted suffix and swaps it into place. It is O(n²) on every input — never adaptive — but it makes the fewest writes of any O(n²) sort, so it can win when writes are far more expensive than reads.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(n²) |
Θ(n²) |
O(n²) |
O(1) |
For i from 0 to n−1: scan arr[i:n] to find the index of the minimum, then swap it with arr[i]. After i+1 iterations, arr[:i+1] is sorted. The number of comparisons is always n(n−1)/2; the number of swaps is exactly n−1.
def selection_sort(arr):
"""In-place selection sort."""
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
print(selection_sort([3, 6, 1, 8, 2, 9, 4])) # [1, 2, 3, 4, 6, 8, 9]