Selection Sort

One Minimum Scan, One Swap

While Bubble Sort swaps repeatedly on its way across the array, Selection Sort separates searching from moving:

1. Partition the array into a sorted prefix a[0 .. i - 1] and an unsorted suffix a[i .. n - 1].
2. Scan every element j in i .. n - 1 to find min_idx, the index holding the smallest value in the suffix.
3. If min_idx != i, swap a[i] and a[min_idx] once.

After pass i, a[i] is smaller than or equal to everything in a[i + 1 .. n - 1] and larger than or equal to everything in a[0 .. i - 1] — it never moves again!

Why Selection Sort Is Non-Adaptive (and Unstable)

• Always Θ(n²) comparisons: Even if the input is already [1, 2, 3, 4, 5], confirming that a[0] really is the minimum of [0 .. n - 1] requires checking all n - 1 remaining slots. Total comparisons are always: (n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2.
• Why long-range swaps break stability: Consider sorting [4ₐ, 4ᵦ, 1]. Pass 0 finds minimum 1 at index 2 and swaps it straight across 4ᵦ with 4ₐ, producing [1, 4ᵦ, 4ₐ] — reversing the relative order of the two 4s!

Clean Python Implementation

def selection_sort(nums: list[int]) -> list[int]:
    """In-place Selection Sort performing at most n - 1 swaps."""
    n = len(nums)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if nums[j] < nums[min_idx]:
                min_idx = j

        if min_idx != i:
            nums[i], nums[min_idx] = nums[min_idx], nums[i]

    return nums

From Selection Sort to Heap Sort

Notice the only bottleneck inside Selection Sort: finding the minimum of the remaining n - i items takes O(n) linear time. Once you replace that flat suffix scan with a Binary Heap (O(log n) extract-max/min), Selection Sort evolves directly into Heap Sort (O(n log n))!