Selection Sort

Selection sort is one of the simplest sorting algorithms to learn: it repeatedly finds the smallest remaining value in a list and moves it into its correct position at the front. It’s rarely used in production code because faster algorithms exist, but it’s a foundational building block for understanding comparison-based sorting, and it has one genuinely useful property — it performs very few swaps compared to other simple sorts, which matters when writes are expensive.

Overview: How Selection Sort Works

Imagine you’re handed a messy stack of exam papers and asked to arrange them by score, lowest to highest, one paper at a time on a table. A natural strategy: scan the entire stack, find the lowest score, and place it at the very front. Then scan the remaining stack (everything except the paper you just placed), find the next-lowest score, and place it right after the first. Repeat until nothing is left. That is exactly what selection sort does with an array.

Concretely, selection sort splits the array into two conceptual regions: a sorted region at the front (initially empty) and an unsorted region covering the rest. On each pass it scans the entire unsorted region to find the index of the smallest value, then swaps that value into the first position of the unsorted region. This grows the sorted region by one element and shrinks the unsorted region by one. After n - 1 passes over an array of length n, the whole array is sorted — the very last element is guaranteed to already be in place once everything before it is, so a final pass isn’t needed.

The key mechanic to internalize: selection sort never moves an element until it has scanned the entire remaining unsorted region and is certain it has found the true minimum. It cannot stop early once it finds “a small enough” value, because it specifically needs the smallest one. This is different from insertion sort, which shifts elements as it goes and can sometimes finish a pass early. In pseudocode, the shape of the algorithm looks like this:

def selection_sort(arr):
    for i in range(0, n - 1):
        min_index = index of the smallest value in arr[i:]
        swap arr[i] and arr[min_index]

Time and Space Complexity

Case	Time Complexity	Why
Best case	O(n^2)	Even on an already-sorted array, selection sort still scans the whole remaining unsorted region on every pass to confirm the minimum — it has no way to detect “already sorted” early and skip work.
Average case	O(n^2)	The number of comparisons is fixed by the algorithm’s structure, not by the input’s arrangement: it is always (n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2, which is O(n^2).
Worst case	O(n^2)	Same reasoning — a reverse-sorted array requires exactly as many comparisons as an already-sorted one.

Space complexity is O(1) auxiliary space: selection sort sorts in place, using only a constant number of extra variables (i, j, min_index) no matter how large the input is — no extra arrays and no recursion stack are involved.

One place selection sort genuinely shines: the number of swaps (writes) is at most n - 1, exactly one per pass, because it only swaps once it has located the true minimum. Compare that to bubble sort, which can perform up to O(n^2) swaps. If writes are expensive relative to comparisons — for example, writing to flash storage with limited write cycles — selection sort’s low write count is a real (if niche) advantage, even though its comparison count is still quadratic like other simple sorts.

Examples

Example 1: Sorting a List of Integers

The canonical implementation tracks the index of the current minimum (min_index) as it scans, and swaps only once per pass, after the scan finishes:

def selection_sort(arr: list[int]) -> list[int]:
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


numbers = [64, 25, 12, 22, 11]
sorted_numbers = selection_sort(numbers)
print(sorted_numbers)

Output:

[11, 12, 22, 25, 64]

Tracing it: pass i = 0 scans the whole array and finds 11 at index 4, swapping it to the front to get [11, 25, 12, 22, 64]. Pass i = 1 scans indices 1–4, finds 12 at index 2, and swaps to get [11, 12, 25, 22, 64]. Pass i = 2 finds 22 at index 3 and swaps to get [11, 12, 22, 25, 64]. Pass i = 3 finds that 25 is already the minimum of the last two elements, so no swap happens. The array is sorted.

Example 2: Selection Sort Is Not Stable

A sorting algorithm is stable if it preserves the relative order of elements that compare as equal. Selection sort is not stable, because swapping a far-away minimum into position i can jump it past other elements that were equal to it. Here we sort tuples by their first element only:

def selection_sort_by_key(arr: list[tuple[int, str]]) -> list[tuple[int, str]]:
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j][0] < arr[min_index][0]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


records = [(3, "a"), (1, "b"), (3, "c"), (2, "d"), (1, "e")]
sorted_records = selection_sort_by_key(records)
print(sorted_records)

Output:

[(1, 'b'), (1, 'e'), (2, 'd'), (3, 'c'), (3, 'a')]

Notice the two records with key 3: (3, "a") originally comes before (3, "c"), but in the output (3, "c") comes first. The swap on pass i = 0 moved (1, "b") to the front, and a later pass pulled (3, "c") ahead of (3, "a") because it happened to be the minimum found during that scan — the algorithm has no concept of “keep equal elements in their original order.” If you need a stable sort, use Python’s built-in sorted() or list.sort() (Timsort), which are stable by design.

Example 3: Selection Sort Does the Same Work Regardless of Input Order

Unlike insertion sort, which can finish in close to O(n) time on nearly-sorted input, selection sort’s comparison count never changes — only its swap count does. This example instruments the algorithm to prove it:

def selection_sort_with_counts(arr: list[int]) -> tuple[list[int], int, int]:
    n = len(arr)
    comparisons = 0
    swaps = 0
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            comparisons += 1
            if arr[j] < arr[min_index]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
            swaps += 1
    return arr, comparisons, swaps


already_sorted = [1, 2, 3, 4, 5]
result, comparisons, swaps = selection_sort_with_counts(already_sorted)
print(f"Sorted: {result}")
print(f"Comparisons: {comparisons}")
print(f"Swaps: {swaps}")

Output:

Sorted: [1, 2, 3, 4, 5]
Comparisons: 10
Swaps: 0

Even though the input was already sorted, the algorithm still performed 4 + 3 + 2 + 1 = 10 comparisons — exactly n(n - 1) / 2 for n = 5 — because it must scan the full remaining region on every pass to be sure nothing smaller exists. The swap count, however, dropped to 0, since min_index always equaled i already. This is the core tradeoff: comparisons are always O(n^2), but swaps scale with how “out of place” the data actually is, up to a maximum of n - 1.

How It Works Step by Step

Trace selection sort on [29, 10, 14, 37, 13] by hand:

Pass (i)	Unsorted region scanned	Minimum found	Array after this pass
0	[29, 10, 14, 37, 13]	10 at index 1	[10, 29, 14, 37, 13]
1	[29, 14, 37, 13]	13 at index 4	[10, 13, 14, 37, 29]
2	[14, 37, 29]	14 at index 2 (no swap needed)	[10, 13, 14, 37, 29]
3	[37, 29]	29 at index 4	[10, 13, 14, 29, 37]

After pass i = 3 (the last pass for n = 5, since the loop runs range(n - 1)), the array is fully sorted: [10, 13, 14, 29, 37]. Notice pass 2 found that index 2 already held the minimum of its region, so min_index == i and no swap was performed — this is why checking if min_index != i before swapping is worth doing, even though skipping it wouldn’t break correctness (swapping an element with itself is harmless, just wasted work).

Common Mistakes

Mistake 1: Comparing Against the Wrong Element

A very easy typo is comparing each candidate against the fixed element arr[i] instead of against the current best candidate arr[min_index]. This silently breaks the “track the running minimum” logic:

def selection_sort_buggy(arr: list[int]) -> list[int]:
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[i]:  # BUG: should compare to arr[min_index]
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


numbers = [5, 3, 4, 1, 2]
print(selection_sort_buggy(numbers))

Output:

[2, 1, 3, 4, 5]

That’s wrong — 1 and 2 are out of order. The bug: once min_index updates to a smaller candidate, later comparisons still check against the original arr[i] rather than the new best candidate, so a later element that’s smaller than arr[i] but larger than the true running minimum can incorrectly overwrite min_index. The fix is to always compare against arr[min_index], since that’s the value that actually has to beat every other candidate:

def selection_sort(arr: list[int]) -> list[int]:
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


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

Output:

[1, 2, 3, 4, 5]

Mistake 2: Using min() Plus list.index() With Duplicate Values

It’s tempting to “simplify” the inner loop by calling the built-in min() on the remaining slice and then looking up its position with arr.index(). This looks correct and even works on arrays without duplicates — but list.index() always searches from the start of the whole list, not from index i, so it can find a copy of the minimum value sitting in the already-sorted prefix and swap with that instead:

def selection_sort_buggy2(arr: list[int]) -> list[int]:
    n = len(arr)
    for i in range(n - 1):
        min_val = min(arr[i:])
        min_index = arr.index(min_val)  # BUG: searches the whole list, not arr[i:]
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


numbers = [1, 3, 1, 2]
print(selection_sort_buggy2(numbers))

Output:

[3, 1, 1, 2]

That is not sorted at all. On pass i = 1, the minimum of arr[1:] is 1, but arr.index(1) returns index 0 — the copy of 1 already placed at the front on the previous pass — so the code swaps the already-sorted element right back out of place. The fix is to manually track the index while scanning only arr[i:], exactly as in the correct implementation, rather than reconstructing the index with a whole-list search:

def selection_sort(arr: list[int]) -> list[int]:
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


numbers = [1, 3, 1, 2]
print(selection_sort(numbers))

Output:

[1, 1, 2, 3]

Best Practices

• For real production code, use Python’s built-in sorted() or list.sort() — both use Timsort, which is O(n log n), stable, and implemented in highly optimized C. Selection sort exists to teach the concept, not to replace the built-in.
• Reach for selection sort (or study it) when swaps/writes are far more expensive than comparisons — its O(n) write bound beats bubble sort’s potential O(n^2) writes.
• Do not use selection sort when you need a stable sort (e.g., sorting rows by one column while preserving original order for ties) — it does not guarantee that. Insertion sort or Timsort do.
• Do not use selection sort expecting it to speed up on nearly-sorted input the way insertion sort does — its comparison count is always O(n^2), regardless of how sorted the input already is.
• Avoid selection sort for large n (roughly beyond a few thousand elements) in real applications; the quadratic comparison cost becomes prohibitive quickly.
• Always compare new candidates against arr[min_index] (the current best), never against a fixed reference like arr[i], to avoid the stale-comparison bug shown above.

Practice Exercises

1. Write selection_sort_descending(arr: list[int]) -> list[int] that sorts in descending order by finding the maximum remaining value on each pass instead of the minimum. Test it on [5, 1, 4, 2, 8]; it should print [8, 5, 4, 2, 1].
2. Using the comparisons/swaps-counting version of selection sort from Example 3, predict (before running it) how many comparisons and how many swaps it will perform on the reverse-sorted list [5, 4, 3, 2, 1]. Then run it and check your prediction.
3. Interview-style: It’s a known fact that the number of swaps selection sort performs to sort an array equals the minimum possible number of swaps needed to sort it (this follows from viewing the array as a permutation made of disjoint cycles). Write min_swaps_to_sort(arr: list[int]) -> int that returns this minimum swap count without needing to preserve the original array. Hint: run the standard selection sort logic on a copy of the array and count only the swaps.

Summary

• Selection sort repeatedly scans the unsorted region for the minimum value and swaps it into place, growing a sorted prefix one element per pass.
• Time complexity is O(n^2) in the best, average, and worst cases — comparisons never decrease no matter how sorted the input already is, because the full remaining region must be scanned every pass.
• Space complexity is O(1) — it sorts in place with only a few extra variables.
• It performs at most n - 1 swaps total, which is fewer than many other simple sorts — useful when writes are expensive.
• Selection sort is not stable: equal elements can end up reordered relative to their original positions.
• Common bugs include comparing against a fixed reference (arr[i]) instead of the running best (arr[min_index]), and using list.index() on a min() result, which searches the whole list and misbehaves with duplicate values.
• In practice, prefer Python’s built-in sorted()/list.sort() (stable, O(n log n) Timsort) over selection sort for anything beyond learning or small, write-sensitive cases.