Selection sort

Cost and properties

compares	~n²/2, always
exchanges	n
in place	yes
stable	no

Reference: Sedgewick & Wayne, §2.1.

Selection sort in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def selection_sort(a):
    # INVARIANT: a[0..i-1] is sorted AND every key there is <= every key right of i.
    n = len(a)
    for i in range(n):
        smallest = i                      # index of the smallest key in a[i..n-1]
        for j in range(i + 1, n):
            if a[j] < a[smallest]:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]
    return a

Why it works

The invariant

Two claims hold at the top of every iteration: a[0..i-1] is in its final sorted order, and nothing to the right of i is smaller than anything to its left. The second half is what makes the left part final rather than merely sorted — selection sort never revisits a placed key.

The cost, and why input does not matter

The inner loop always scans the whole remaining array: (n−1) + (n−2) + … + 1 = ~n²/2 compares, on every input. Only n exchanges though — the fewest of any elementary sort, which is its one real advantage: use it when moving data is far more expensive than comparing it.

Not stable

The long-range swap can jump one equal key past another. With keys B₁ B₂ A, the first pass swaps A with B₁ and the two Bs come out in the wrong relative order. If you need stability, use insertion sort or mergesort.

Watch for

• smallest updates only on a strictly smaller key, so the earliest of several equal minima wins.
• The final exchange happens even when smallest == i — a wasted write the textbook version keeps for simplicity.

What to try in the animation

Try already sorted and reverse sorted: the compare count does not move. That is the defining weakness.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• random — 7 10 5 3 8 4 2 9 6 1
• SORTEXAMPLE (course) — S O R T E X A M P L E
• already sorted — 1 2 3 4 5 6 7 8 9 10
• reverse sorted — 10 9 8 7 6 5 4 3 2 1
• all equal — 5 5 5 5 5 5 5 5
• few distinct — 2 1 2 1 3 1 2 3 1 2

Open Selection sort in the player →

The rest of Elementary sorts

• Insertion sort Slide each key left until it lands. Its cost is exactly the number of inversions in the…
• Shellsort Insertion sort, but comparing keys h apart.
• Knuth shuffle Swap each item with a random earlier one.