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])

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.