Selection sort

Brute force

In each round, find the smallest item of the unsorted part and move it to the front of that part.

The array has two parts: the sorted part at the front and the unsorted part after it. In each round, the smallest item of the unsorted part is found and swapped with the first item of that part. After round i, position i holds its final item.

Read the full explanation ↓

Time: O(n²)
Space: O(1)
CLRS, section 2.2
Horowitz–Sahni, chapter 1

Input:

n=5PDF export

Five mixed numbers; four rounds, each putting one item in its final place.

def selection_sort(a):
n = len(a)
for i in range(n - 1):
smallest = i
for j in range(i + 1, n):
if a[j] < a[smallest]:
smallest = j
a[i], a[smallest] = a[smallest], a[i]
return a

Invariant: At the start of each round, a[0..i−1] holds the i smallest items of the array, in order.

Start

Local variables

Orange = changed in this step

`a` list

6425122211

Call stack

selection_sort()line 1

Step 1 of 45

How the work grows with input size

Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.

comparisons
swaps
current input (n=5)

Show as a table

n	comparisons	swaps
4	6	3
6	15	5
8	28	7
10	45	9
12	66	11
14	91	13
16	120	15

Explanation

The idea

Cost

The number of comparisons is always n(n − 1)/2, whatever the input: O(n²).
There are at most n − 1 swaps; when writing to memory is expensive, that is a real advantage.
Extra memory O(1).

Stability

Swapping the smallest item with a[i] can move an item past an equal one, so selection sort is not stable.

What to watch in the trace

The smallest arrow shows the smallest item so far, and j walks through the rest.
Compare the number of compare steps on "already sorted" and "sorted backwards": it is the same.