~/blog

Selection Sort

Jun 2, 2026•8 min read•By Mohammed Vasim

dsapythondata-structuresalgorithmsproblem-solving

Why Minimising Swaps Matters

Bubble sort swaps every adjacent pair that is out of order — up to O(n²) swaps. Insertion sort shifts elements — also O(n²) moves. Selection sort takes a different approach: it scans the unsorted portion to find the minimum, then swaps that single element into the correct position. Exactly one swap per pass, n-1 swaps total.

When writes are expensive (flash memory, EEPROM with limited write cycles), selection sort is the right choice despite its O(n²) comparisons.

Example

Tracing [29, 10, 14, 37, 13, 33].

The array is divided into sorted (left) and unsorted (right) portions. Initially, the sorted portion is empty.

Pass 1 — find minimum in indices 0–5

Scan index	arr[index]	Current minimum candidate	Minimum index so far	Update?
0	29	29	0	Initial
1	10	10	1	10 < 29 → update
2	14	10	1	14 > 10 → keep
3	37	10	1	37 > 10 → keep
4	13	10	1	13 > 10 → keep
5	33	10	1	33 > 10 → keep

Minimum is 10 at index 1. One swap: arr[0] ↔ arr[1] → [10, 29, 14, 37, 13, 33].

Pass 2 — find minimum in indices 1–5

Minimum is 13 at index 4. Swap arr[1] ↔ arr[4] → [10, 13, 14, 37, 29, 33].

Pass 3 — find minimum in indices 2–5

Minimum is 14 at index 2. Self-swap (no change) → [10, 13, 14, 37, 29, 33].

Pass 4 — find minimum in indices 3–5

Minimum is 29 at index 4. Swap arr[3] ↔ arr[4] → [10, 13, 14, 29, 37, 33].

Pass 5 — find minimum in indices 4–5

Minimum is 33 at index 5. Swap arr[4] ↔ arr[5] → [10, 13, 14, 29, 33, 37] · sorted.

Complexity

Time: O(n²) — always. Best, average, and worst cases all require n(n-1)/2 comparisons. This is selection sort's weakness: it does not exploit existing order. An already-sorted array requires the same number of comparisons as a reverse-sorted one. Space: O(1).

The number of swaps is exactly n-1. Bubble sort can make up to n(n-1)/2 swaps. For write-limited hardware, this difference matters.

Code

python

def selection_sort(arr):
    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

Line by line:

for i in range(n - 1): — the sorted portion grows from the left. After pass i, arr[0..i] contains the smallest i+1 elements. n - 1 passes suffice because the last element is automatically in place once the other n-1 are sorted.
min_idx = i — assume the first unsorted element is the minimum.
for j in range(i + 1, n): — scan the rest of the unsorted portion.
if arr[j] < arr[min_idx]: — found a smaller element.
min_idx = j — remember the new minimum. Without this update, the algorithm would always swap arr[i] with itself.
if min_idx != i: — skip self-swaps. No-ops are harmless but waste time.
arr[i], arr[min_idx] = arr[min_idx], arr[i] — place the minimum at the boundary between sorted and unsorted.

Edge case — single element. range(0) — zero passes. Returns immediately.

Edge case — all identical. arr[j] < arr[min_idx] is never true. min_idx always equals i. No swaps. Correct.

Code Trace

Tracing selection_sort([29, 10, 14, 37, 13, 33]):

Pass i	min_idx start	j range	Minimum found at	Swap?	Array after
0	0	1–5	idx 1 (value 10)	0 ↔ 1	[10, 29, 14, 37, 13, 33]
1	1	2–5	idx 4 (value 13)	1 ↔ 4	[10, 13, 14, 37, 29, 33]
2	2	3–5	idx 2 (value 14)	No (i == min_idx)	—
3	3	4–5	idx 4 (value 29)	3 ↔ 4	[10, 13, 14, 29, 37, 33]
4	4	5	idx 5 (value 33)	4 ↔ 5	[10, 13, 14, 29, 33, 37]

Total comparisons: 5 + 4 + 3 + 2 + 1 = 15 = n(n-1)/2. Total swaps: 4 (pass 2 skipped because the minimum was already at the boundary).

Selection sort's guarantee of exactly n-1 swaps makes it a niche tool for write-constrained environments. For general-purpose sorting, merge sort (guaranteed O(n log n)) or Timsort (adaptive O(n log n)) are better choices.

→ LeetCode 912: Sort an Array — selection sort passes small test cases but times out on large ones.