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.
This page walks through the algorithm pass by pass, explains why its write count is minimal, and shows when that property is worth the quadratic comparison cost.
| 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]The trace shows the array after each outer-loop iteration. In pass i the algorithm scans positions i through n-1, finds the smallest value, and swaps it into position i. Everything to the left of i is in its final place and is never touched again. In pass i=0 the minimum of the whole array is 1, which trades places with 3; in pass i=1 the minimum of the suffix [6, 3, 8, 2, 9, 4] is 2, which trades places with 6. In a pass where the minimum is already at position i (as with 3 at i=2 and 6 at i=4 here), the implementation skips the swap entirely. Seven elements need six passes; the last element is necessarily the maximum once the others are placed.
Selection sort separates the reading phase from the writing phase. The inner loop only compares and records an index, so it performs no stores to the array. The single swap at the end of each pass is the only write. That gives exactly n(n−1)/2 comparisons regardless of input order, and at most n−1 swaps. Insertion sort, by contrast, can shift O(n²) elements in the worst case, and bubble sort can perform O(n²) swaps. When each write is expensive — flash pages with limited erase cycles, or records that are physically large and costly to move — minimising writes can matter more than minimising comparisons.
def selection_sort_counted(arr):
a = list(arr)
comps = swaps = 0
for i in range(len(a) - 1):
m = i
for j in range(i + 1, len(a)):
comps += 1
if a[j] < a[m]:
m = j
if m != i:
a[i], a[m] = a[m], a[i]
swaps += 1
return a, comps, swaps
for data in ([3, 6, 1, 8, 2, 9, 4], list(range(7)), list(range(7, 0, -1))):
print(data, selection_sort_counted(data)[1:])
# comparisons are 21 for every input of length 7; swaps vary from 0 to 6Running this on random, sorted and reverse-sorted input of the same length shows the comparison count is identical (21 for n=7), which is what “not adaptive” means in practice. Only the swap count changes. Reverse-sorted input of length 7 needs just 3 swaps, because each swap places two elements correctly once the middle is reached.
Use selection sort when n is small and writes are costly, or as a teaching example for loop invariants: after pass i, the prefix a[:i+1] holds the i+1 smallest values in order. For general-purpose sorting, insertion sort is faster on small or nearly sorted inputs and a library O(n log n) sort is the right default for anything larger. Heapsort can be viewed as selection sort with the linear minimum scan replaced by a heap, which brings the cost down to O(n log n) while keeping the in-place property. Cycle sort goes one step further and achieves the theoretical minimum number of writes, at the cost of even more comparisons, which makes it a curiosity outside of write-limited storage. In interviews, selection sort is mostly useful as a baseline to contrast with insertion sort: same complexity class on paper, very different behaviour on real data.
See the Simple Sorts overview for a side-by-side comparison with Insertion Sort, Bubble Sort and Shell Sort, and Mergesort for an O(n log n) alternative.