Selection sort explained: how it works, code and complexity

The idea in plain words

Scan the whole list and find the smallest element. Swap it with the element at index 0; now index 0 is final. Scan the rest of the list from index 1, find the smallest, and swap it into index 1. Continue until only one element is left, which must be the largest.

Unlike bubble sort and insertion sort, selection sort does not benefit from input that is already sorted: it still has to scan every remaining element to be sure it found the minimum.

Worked example, step by step

Sort [64, 25, 12, 22, 11]. The part before the bar is sorted and final.

Four steps for five elements, with 4 + 3 + 2 + 1 = 10 comparisons and three real swaps.

Python implementation

def selection_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        if smallest != i:
            items[i], items[smallest] = items[smallest], items[i]
    return items
print(selection_sort([64, 25, 12, 22, 11]))   # [11, 12, 22, 25, 64]
print(selection_sort([2, 1]))                 # [1, 2]

The outer loop runs n − 1 times because the last remaining element is automatically in place. The inner loop only records an index; the swap happens once per outer step.

Time and space complexity

The small number of writes is the one real strength of selection sort. If writing to memory is much more expensive than reading, as with some flash memory or when moving large records, fewer writes can matter. Cycle sort takes this further and writes each element at most once.

Stability: why selection sort is not stable

A stable sort keeps equal elements in their original relative order. The long-distance swap in selection sort can jump an element over another one that is equal to it.

def selection_sort_by_key(items, key):
    n = len(items)
    for i in range(n - 1):
        m = min(range(i, n), key=lambda j: key(items[j]))
        items[i], items[m] = items[m], items[i]
    return items
cards = [("4", "hearts"), ("4", "spades"), ("2", "clubs")]
print(selection_sort_by_key(cards, key=lambda c: c[0]))
# [('2', 'clubs'), ('4', 'spades'), ('4', 'hearts')]  order of the 4s changed

The 2 was swapped with the 4 of hearts, which moved the 4 of hearts behind the 4 of spades. A stable version exists: instead of swapping, remove the minimum and insert it at position i, shifting the others right. This keeps the order but costs O(n) writes per step.

How selection sort compares with other sorts

Heapsort is selection sort with a better data structure: it also repeatedly selects the largest remaining element, but finds it in O(log n) using a binary heap instead of an O(n) scan, which brings the total to O(n log n).

When to use selection sort

Use the built-in sorted() or list.sort() in real Python code. Selection sort is worth knowing as a teaching example, for very small fixed-size arrays in constrained environments, and when the number of writes must be minimal. It is a frequent exam and interview question, usually as: trace the steps, count the comparisons and swaps, and explain why it is not stable.