Selection SortSelection sort

01Why it exists

Reach for it when you see:Minimising swaps or writes, cheap comparisons but expensive moves, locking in one final position per pass, only needing the first few elements, minimum number of swaps, small data where stability does not matter.

02The core idea

Selection sort splits the array in two: a sorted region on the left and an unsorted region on the right. Each pass scans the unsorted region from end to end, remembering the index of the smallest value, and then swaps that value into the first slot of the unsorted region — so the sorted region grows by one. After n−1 passes the first n−1 slots are settled, and whatever is left in the final slot must be the largest, so it needs no pass of its own.

Correctness rests on one invariant: after pass i (counting from 0), a[0..i] holds the i+1 smallest elements of the whole array, in ascending order. At the start of that pass, every element of the unsorted region is at least as large as everything in the sorted region; pulling out the smallest of them and putting it in a[i] neither breaks the order nor risks anything smaller being left behind, and the induction goes through. Unlike bubble sort, which nudges the maximum to the end one adjacent swap at a time, selection sort only records an index and then uses a single swap to send the element straight to its final home — hence at most n−1 swaps. Push that further: connect each slot to the position its element belongs in once sorted and you get a set of cycles, and every swap peels exactly one settled element off a cycle. So when the elements are all distinct, the number of swaps is exactly n − the number of cycles, which is the fewest swaps any swap-only sort can manage.

Complexity: pass i makes n−1−i comparisons, for a total of (n−1) + (n−2) + … + 1 = n(n−1)/2. That number is independent of the input: you cannot know which element is smallest without looking at every slot in the unsorted region, so there is no early exit to be had. Best, average and worst case are all Θ(n²) comparisons — an already-sorted array still costs n(n−1)/2 comparisons, it just costs 0 swaps. Swaps top out at n−1 and writes are O(n), and since the only extra state is one index variable, the extra space is O(1).

The property most often overlooked is that selection sort is not stable: a swap flings a[i] off to the back, possibly past an element equal to it. Sorting [(3, A), (3, B), (1, C)] by score, the first pass swaps (3, A) with (1, C) and leaves [(1, C), (3, B), (3, A)] — A and B have traded places. Making it stable means lifting the minimum out, shifting everything in between one slot right, and putting it back, which pushes writes to O(n²) and throws away the algorithm's greatest strength. Another common mistake is swapping inside the inner loop the moment something smaller appears, which degrades the swap count to O(n²); the inner loop should only update the index. Against the neighbours: bubble sort makes exactly as many swaps as there are inversions, but it is stable and can exit early; insertion sort is O(n) on nearly sorted data and is what people actually reach for on small arrays; and heapsort is selection sort upgraded, replacing the linear scan for the extreme value with a heap's O(log n), which brings the whole thing down to O(n log n).

03The algorithm

1. 1The outer loop runs i from 0 to n−2. At that point a[0..i−1] is sorted and a[i..n−1] is the unsorted region.
2. 2Set m = i. The inner loop scans j from i+1 to n−1 and sets m = j whenever a[j] < a[m]. The inner loop only updates the index; it never swaps.
3. 3Once the inner loop finishes, swap a[i] with a[m] if m ≠ i. From here on a[i] holds its final value and is never touched again.
4. 4The last slot needs no pass: the first n−1 slots took all the smaller elements, so whatever is left must be the largest. To sort descending, flip the comparison to > and pick the maximum each pass.
5. 5If you only want the k smallest, stop the outer loop after k passes and a[0..k−1] is the answer, in O(kn). If you need stability, replace the swap with "lift out a[m], shift a[i..m−1] right by one, drop it into a[i]".

04Interactive demo

The same array as bubble sort, [5, 2, 9, 1, 7, 3, 8, 4], sorted ascending. Each step looks at one slot of the unsorted region: blue is the slot being examined, yellow is the current minimum candidate, and yellow jumps whenever something smaller turns up. At the end of a pass the two blue slots are that pass's one and only swap, and green is the sorted region on the left. Notice that in passes 2 and 7 the minimum is already in place, so no swap happens. The run ends with 28 comparisons and just 5 swaps (this data has 3 cycles, and 8 − 3 = 5, which is the minimum). Bubble sort needs 13 swaps on the same array.

05Code

The basic version returns the swap count so you can compare it directly with bubble sort. The two variants are the k-pass version that extracts the k smallest, and the stable version that shifts right instead of swapping. The main program runs both the plain and the stable version over records with tied scores, so you can see how swapping scrambles the order of equal elements. The C++ version takes a template plus a comparison function, so one body sorts integers and records alike.

# Selection sort: each pass finds the smallest value in the unsorted region and swaps it into that region's first slot.
# Returns the swap count, so it is easy to compare against the other sorts.
def selection_sort(a, key=lambda x: x):
    n = len(a)
    swaps = 0
    for i in range(n - 1):                  # the last slot never needs a pass
        m = i                               # only track the index of the minimum, do not swap yet
        for j in range(i + 1, n):
            if key(a[j]) < key(a[m]):
                m = j
        if m != i:
            a[i], a[m] = a[m], a[i]         # at most one swap per pass, and a[i] is final from here on
            swaps += 1
    return swaps


# Variant 1: run only the first k passes and a[:k] holds the k smallest, already sorted. O(kn)
def smallest_k(a, k):
    n = len(a)
    for i in range(min(k, n)):
        m = min(range(i, n), key=a.__getitem__)   # index of the first minimum in the unsorted region
        a[i], a[m] = a[m], a[i]
    return a[:k]


# Variant 2: the stable version. Instead of swapping, shift a[i..m-1] right by one and drop the minimum into a[i].
# Equal elements keep their relative order, but writes become O(n²), which costs selection sort its best feature.
def stable_selection_sort(a, key=lambda x: x):
    n = len(a)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if key(a[j]) < key(a[m]):       # strictly less: on a tie, keep the earlier element
                m = j
        x = a[m]
        while m > i:                        # shift right, never stepping over an equal element
            a[m] = a[m - 1]
            m -= 1
        a[i] = x
    return a


if __name__ == "__main__":
    a = [5, 2, 9, 1, 7, 3, 8, 4]
    swaps = selection_sort(a)
    print(a, swaps)                         # [1, 2, 3, 4, 5, 7, 8, 9] 5
    print(smallest_k([5, 2, 9, 1, 7, 3, 8, 4], 3))   # [1, 2, 3]

    # Sort by score; A originally sits before B at the same score
    recs = [(3, "A"), (3, "B"), (1, "C")]
    selection_sort(recs, key=lambda r: r[0])
    print(recs)          # [(1, 'C'), (3, 'B'), (3, 'A')]  A and B came out reordered
    recs = [(3, "A"), (3, "B"), (1, "C")]
    stable_selection_sort(recs, key=lambda r: r[0])
    print(recs)          # [(1, 'C'), (3, 'A'), (3, 'B')]

06Practice

• LeetCode 414Third Maximum Number (three "pick the largest" passes, with duplicates counted once)Easy
• LeetCode 2500Delete Greatest Value in Each Row (every pass picks the largest value in each row)Easy
• LeetCode 670Maximum Swap (a descending selection sort that makes a single swap)Medium
• LeetCode 969Pancake Sorting (every pass flips the largest value to the end)Medium
• LeetCode 2471Minimum Number of Operations to Sort a Binary Tree by Level (minimum swaps = n − number of cycles)Medium
• LeetCode 765Couples Holding Hands (another minimum-swaps problem)Hard