Selection Sort Explained: n² Comparisons, at Most n − 1 Swaps

Selection sort is usually taught as the simplest quadratic sort and then forgotten. That undersells it. It has a property no other textbook sort shares: it moves each value at most once, so it writes far less than bubble or insertion sort. And it has a flaw that interviewers like to ask about, because it is easy to miss: the plain version is not stable. Both facts come straight out of how one round works.

The problem it solves

Sort an array in place, with constant extra memory, using only comparisons and swaps. Any quadratic sort does that. What sets selection sort apart is where its cost goes:

• Comparisons: exactly n(n-1)/2, on every input. Sorted, reversed or random, the count does not change.
• Swaps: at most n - 1. Each round ends with one swap, or none if the value is already in place.

So it is the sort to reach for when comparing is cheap and writing is expensive: a small array in flash memory with limited write endurance, or records so large that moving one costs far more than comparing two keys. Everywhere else, insertion sort or a library sort is the better choice.

The intuition

Split the array into a sorted front and an unsorted tail. At the start the front is empty.

Each round scans the whole tail for its smallest value and swaps it into the first tail slot. That slot now holds the right value for good: everything to its left is smaller, everything to its right is at least as large. The front grows by one and the tail shrinks by one.

The scan is why the comparison count is fixed. To be sure a value is the smallest, the round has to look at every other candidate, even if the tail is already in order. Nothing in the loop ever stops early. Round i compares n - 1 - i pairs, and the sum over all rounds is n(n-1)/2.

The swap is why the write count is small. A value is written into its final slot once and never touched again. The last slot needs no round at all, since a single leftover value is already in place.

The swap is also why the sort is not stable. Moving the smallest value forward throws the value that was in its slot to wherever the smallest one came from, and that jump can carry it past an equal key. Two fives that started as hearts then spades can finish as spades then hearts.

Watch it run

The animation sorts 4 1 5 2 6 3. In round one, 1 beats 4 and becomes the new smallest; 5, 2, 6 and 3 are each checked and are not smaller than 1, and the round ends by swapping the smallest remaining value into index 0. Round two starts at 5: 2 beats 4 and takes over, nothing else does, and 2 goes to index 1. In round three, 4 beats 5 and then 3 beats 4, so 3 goes to index 2. In round four the smallest value was already at index 3, so no swap is needed. In the last round 5 beats 6 and is swapped into index 4. The closing frame gives the count: always 15 comparisons, O(n²) no matter the input, but only 4 swaps, which is why it wins when writing is expensive.

The code

The version below counts both costs, skips the pointless self-swap, and stops one round early:

def selection_sort(nums):
    nums = list(nums)
    comparisons = swaps = 0
    for i in range(len(nums) - 1):          # the last slot is settled for free
        smallest = i
        for j in range(i + 1, len(nums)):   # scan the whole unsorted tail
            comparisons += 1
            if nums[j] < nums[smallest]:
                smallest = j
        if smallest != i:                   # skip the pointless self-swap
            nums[i], nums[smallest] = nums[smallest], nums[i]
            swaps += 1
    return nums, comparisons, swaps

print(selection_sort([4, 1, 5, 2, 6, 3]))   # ([1, 2, 3, 4, 5, 6], 15, 4)
print(selection_sort([1, 2, 3, 4, 5, 6]))   # ([1, 2, 3, 4, 5, 6], 15, 0)
print(selection_sort([2, 3, 4, 5, 6, 1]))   # ([1, 2, 3, 4, 5, 6], 15, 5)

Sorted input still costs 15 comparisons, and the last input hits the n - 1 swap ceiling. Instability shows up as soon as records carry more than their key. A stable variant exists: shift the block instead of swapping, which keeps equal keys in order and gives up the low write count:

def selection_sort_by(items, key):
    items = list(items)
    for i in range(len(items) - 1):
        smallest = min(range(i, len(items)), key=lambda j: key(items[j]))
        items[i], items[smallest] = items[smallest], items[i]
    return items

cards = [(5, "hearts"), (5, "spades"), (2, "clubs")]
print(selection_sort_by(cards, key=lambda c: c[0]))
# [(2, 'clubs'), (5, 'spades'), (5, 'hearts')]  -- the two fives swapped order


def stable_selection_sort_by(items, key):
    items = list(items)
    for i in range(len(items) - 1):
        smallest = min(range(i, len(items)), key=lambda j: key(items[j]))
        items.insert(i, items.pop(smallest))   # shift instead of swap: order kept
    return items

print(stable_selection_sort_by(cards, key=lambda c: c[0]))
# [(2, 'clubs'), (5, 'hearts'), (5, 'spades')]

How much writing does it save? On a reversed array of 100 values, each swap is two writes, against the adjacent swaps insertion sort needs to remove every inversion:

def insertion_sort_writes(nums):
    nums, writes = list(nums), 0
    for i in range(1, len(nums)):
        j = i
        while j > 0 and nums[j - 1] > nums[j]:
            nums[j - 1], nums[j] = nums[j], nums[j - 1]
            writes += 2
            j -= 1
    return writes

data = list(range(100, 0, -1))             # reversed: the worst case for both
print(2 * selection_sort(data)[2], insertion_sort_writes(data))   # 100 9900

Checked on 2,000 seeded random arrays with many duplicates: the result must equal sorted(), the comparison count must be exactly n(n-1)/2, the swaps at most n - 1, and the stable variant must match Python's stable sorted on tagged records:

import random

random.seed(27)
ok = True
for _ in range(2_000):
    n = random.randint(0, 30)
    nums = [random.randint(-5, 5) for _ in range(n)]
    result, comparisons, swaps = selection_sort(nums)
    ok &= result == sorted(nums)
    ok &= comparisons == n * (n - 1) // 2   # same count for every input of size n
    ok &= swaps <= max(n - 1, 0)
    tagged = [(v, k) for k, v in enumerate(nums)]
    ok &= stable_selection_sort_by(tagged, key=lambda t: t[0]) == sorted(tagged, key=lambda t: t[0])
print(ok)                                  # True

The complexity

• Time: O(n²) in the best, average and worst case, because the comparison count depends only on n. The Big-O cheat sheet lists it next to the other sorts for that reason.
• Swaps: at most n - 1, so O(n) writes. The stable shifting variant gives this up and makes O(n²) moves.
• Space: O(1) extra.
• Stable: no, unless you shift instead of swap. Adaptive: no; sorted input earns nothing.

Where it goes wrong

• Claiming an O(n) best case. That belongs to bubble sort with an early exit and to insertion sort. Selection sort has no early exit to add.
• Calling it stable. The long-distance swap reorders equal keys, as the card example shows.
• Using it on large inputs. Quadratic comparisons dominate quickly; the write savings only matter when writes are the bottleneck.
• Forgetting that it is the ancestor of heap sort. Select the minimum, place it, repeat: heap sort runs the same loop with a heap, so each selection costs O(log n) instead of O(n).

When it shows up in interviews

Rarely as a coding question, and often as a comparison question: which simple sort is stable, which one is adaptive, which one does the fewest writes, why is the best case still quadratic. It also appears as an explanation step: "pick the smallest remaining" is the same idea behind heap sort, and the partial version, stopping after k rounds, is a correct but slow way to get the k smallest items.

How to say it in an interview

"Each round scans the unsorted tail for its minimum and swaps it into the next position, which is then final. Finding a minimum means looking at every candidate, so it always makes n times n minus one over two comparisons, even on sorted input: O(n²) in every case. But each value moves at most once, so it makes at most n minus one swaps, which is useful when writes are expensive. The swap can jump a value past an equal key, so it is not stable unless I shift the block instead, and then I lose the low write count."