Selection Sort

Start here Sorting makes many jobs easy: binary search, finding the median (the middle value), spotting duplicates (they sit next to each other), making a frequency table. Our first sorting method is the one you would invent yourself: keep picking the smallest thing that is left.

The idea — a teaching assistant with exam papers #

You are a TA. The teacher hands you a pile of checked exam papers in random order of marks. You must arrange them by marks.

Strategy 1:

1. Scan the whole pile and find the paper with the minimum marks.
2. Move it to a new pile.
3. Repeat with the papers that are left, each time adding the next minimum to the new pile.

Each new paper goes on top, so in the end the new pile, read from the top, is in descending order — highest marks on top, lowest at the bottom. That's selection sort: repeatedly select the minimum.

Doing it in the same list (in place) #

We don't need a second list. Instead:

• Find the minimum of the whole list and swap it into position 0.
• Find the minimum of the rest (positions 1 onward) and swap it into position 1.
• ... and so on.

After step i, the first i + 1 positions hold the smallest items, in order.

Full trace — sort [74, 32, 89, 55, 21, 64] #

The <b>sorted part</b> is on the left (before the bar |).

Sorted: 21, 32, 55, 64, 74, 89 ✔

The code #

def SelectionSort(L):
    n = len(L)
    if n < 1:
        return L
    for i in range(n):
        # Assume L[:i] is sorted
        mpos = i                      # mpos: position of minimum in L[i:]
        for j in range(i+1, n):
            if L[j] < L[mpos]:
                mpos = j
        # L[mpos] is the smallest value in L[i:]
        (L[i], L[mpos]) = (L[mpos], L[i])   # swap it into position i
        # Now L[:i+1] is sorted
    return L

Why is it correct? — the invariant #

An invariant is a statement that stays true every time the loop goes round. Here:

At the start of pass i, L[:i] holds the i smallest items, in sorted order.

• It's true at the start (i = 0: L[:0] is empty).
• Each pass adds the next smallest item at position i, so it stays true.
• When the loop ends (i = n), L[:n] — the whole list — is sorted. ✔

How long does it take? #

In pass i, the inner loop scans positions i+1 to n−1: that's n − 1 − i comparisons.

For n = 6:

In general: (n − 1) + (n − 2) + ... + 1 + 0 = n(n − 1)/2 comparisons. (The slide counts n − i steps per pass, giving n(n + 1)/2 — same order.)

T(n) is O(n²).

Every input takes this long #

Selection sort always scans the whole unsorted part, even if the list was already sorted. It never "notices" good order.

We counted comparisons for n = 1000:

Exactly the same every time = 1000 × 999 / 2. So for selection sort, best case = worst case = O(n²).

Tried it ourselves: on random lists, doubling n made selection sort about 4 times slower (n = 1000 → 0.02 s, 2000 → 0.09 s, 4000 → 0.41 s). That's the n² signature: (2n)² = 4n².

In one line: Selection sort repeatedly picks the minimum of the unsorted part and swaps it to the front; it always takes n(n−1)/2 comparisons → O(n²).

Exam words: selection sort, minimum, swap, in place, invariant, L[:i] sorted, n(n−1)/2, O(n²), best case = worst case.

Quick check #