0

Selection Sort

Easy

Repeatedly find the smallest remaining value and swap it into the next position. Always n squared comparisons, but at most n swaps.

comparison sortin placeunstable
TimeO(n^2) always
SpaceO(1)
InputComma separated numbers
64
0
25
1
12
2
22
3
11
4

Find the minimum of the unsorted suffix, then place it.

comparisons0swaps0
1 / 27
for i from 0 to n-1:
minIdx = i
for j from i+1 to n-1:
if a[j] < a[minIdx]: minIdx = j
swap(a[i], a[minIdx])
Why it matters

Minimal number of writes, which matters when writes are expensive.

Keyboard
space play← → stepr restartctrl K search

More in Sorting

Quickselect
O(n) expected, O(n^2) worst
Bubble Sort
O(n^2), best O(n) when already sorted
Insertion Sort
O(n^2), O(n) on nearly sorted input
Merge Sort
O(n log n) always
Quick Sort
O(n log n) average, O(n^2) worst
Counting Sort
O(n + k)
Next visualiser
Insertion Sort