Selection Sort — Pick the Minimum, Repeat

Selection sort repeatedly selects the smallest remaining element and swaps it into the front. It minimizes writes but still needs O(n²) comparisons—simple but rarely optimal.

Why this shows up in the real world

Flash memory wear research sometimes cares about write cycles; selection-style moves can reduce writes compared to shifting-heavy sorts on tiny buffers. Embedded displays updating a ranked list of three metrics might pick the cheapest field to rewrite. Again, small n only.

Core idea (explained for students)

Outer loop i chooses the position to fill; inner loop scans i..n-1 for the minimum index m, then swap a[i] with a[m]. Not stable when swapping non-adjacent equal keys. Comparisons Θ(n²); swaps O(n).

Try this in Python

def selection_sort(a):
    a = a[:]
    for i in range(len(a)):
        m = min(range(i, len(a)), key=lambda k: a[k])
        a[i], a[m] = a[m], a[i]
    return a


print(selection_sort([4, 5, 1, 3, 2]))

Common mistakes

• Trying to make it stable without extra space—hard.
• Off-by-one inner scan end.
• Using on large arrays in production.

Key takeaways

• O(n) swaps, O(n²) comparisons.
• Unstable in textbook form.
• Pedagogical stepping stone to heaps (pick min repeatedly).