Selection Sort

Selection sort repeatedly finds the smallest remaining value and swaps it into the next position, growing a sorted part from the left.

Start

5
3
8
2
9
1
4
  • Smallest so far
  • Comparing
  • Moving
  • In final place

Selection sort finds the smallest remaining value and puts it next in line — over and over.

Step 1 / 41
Comparisons
0
Swaps
0
for i from 0 to n − 2:
min = i
for j from i + 1 to n − 1:
if a[j] < a[min]: min = j
swap(a[i], a[min])

Step by step

The example above, written out — the same steps the animation plays.

  1. 1Start. Selection sort finds the smallest remaining value and puts it next in line — over and over.
  2. 2Find the smallest from position 0. Start by assuming 5 is the smallest.
  3. 3Is 3 smaller than 5?. Yes — 3 is the new smallest.
  4. 4Is 8 smaller than 3?. No — 3 is still the smallest.
  5. 5Is 2 smaller than 3?. Yes — 2 is the new smallest.
  6. 6Is 9 smaller than 2?. No — 2 is still the smallest.
  7. 7Is 1 smaller than 2?. Yes — 1 is the new smallest.
  8. 8Is 4 smaller than 1?. No — 1 is still the smallest.
  9. 9Swap 1 into place. 1 swaps with 5 and is now final.
  10. 101 is in place. Position 0 is done.
  11. 11Find the smallest from position 1. Start by assuming 3 is the smallest.
  12. 12Is 8 smaller than 3?. No — 3 is still the smallest.
  13. 13Is 2 smaller than 3?. Yes — 2 is the new smallest.
  14. 14Is 9 smaller than 2?. No — 2 is still the smallest.

…and 27 more steps — press Play above to watch them all.

What's happening?

  1. Scan the unsorted part, remembering the smallest value seen so far.
  2. Swap that smallest value into the first unsorted position — it is now final.
  3. Repeat on what is left, one position further right each time.

Complexity

Time
O(n²) always — even on sorted input
Space
O(1) — sorts in place

Where you'll meet it

Rarely used for big data, but it makes the fewest swaps of the simple sorts — useful when writing is expensive (for example to flash memory).

Common mistake

Thinking sorted input makes it faster. It still compares every remaining pair: n(n−1)/2 comparisons, whatever the order.

FAQ

Is selection sort stable?

Not in its usual form: the long-distance swap can jump an equal value past another.

How many swaps does it make?

At most n − 1 — one per position — far fewer than bubble sort.

Selection vs insertion sort?

Selection sort always does the same number of comparisons; insertion sort adapts and is faster on nearly sorted data.