Home/Sorting/Selection sort
Search algorithmsCTRL K

Selection sort

· selection · minimum to the front
/sorting/selection-sort
COMPARISONS
0
n(n−1)/2 always
SWAPS
0
at most n − 1
PASS
0/ 23
slot being filled
MINIMUM
—
candidate so far
IN PLACE
0/ 24
the sorted prefix
slotcomparingswappedin place
n = 24 · seed 7 · 324 steps
step 0 / 323
Size24
selection_sort.ts
1
function selectionSort(array: number[]) {
2
  for (let i = 0; i < array.length - 1; i++) {
3
    let minIndex = i;
4
    for (let j = i + 1; j < array.length; j++) {
5
      if (array[j] < array[minIndex]) minIndex = j;
6
    }
7
    if (minIndex !== i) [array[i], array[minIndex]] = [array[minIndex], array[i]];
8
  }
9
}
CURRENT STEP
line 1

Start: 24 values. Each pass finds the minimum of the rest and swaps it to the front.

// how it works

Understanding Selection sort

selection sort · n − 1 swaps, no matter what
01

The idea

Selection sort splits the array into a sorted prefix and the rest. On each pass it scans the rest for the minimum and swaps it into the first unsorted position. After pass i the prefix of length i + 1 is final, and nothing in it ever moves again.

The scan is what costs: finding the minimum of k elements takes k − 1 comparisons, and the passes add up to n²/2 comparisons regardless of the input. The swap count is the flip side: at most one per pass, n − 1 in total.

02

The four stages

1
slotposition i receives the next minimum
2
scancompare every array[j] with the candidate
3
swapminimum into array[i]
4
settlearray[i] is final, i moves right
03

Complexity

best
O(n²)the scan never shortens, sorted or not
average
O(n²)n²/2 comparisons, n − 1 swaps
worst
O(n²)same as the best: input does not matter
space
O(1)in place
04

Versus its siblings

SWAPS AT N = 1 000
bubble
249,750
insertion
249,750
heap
9,500
quick
6,900
selection
999
random input · insertion counts shifts, quick uses Lomuto
05

Pseudocode

SELECTIONSORT(array)
  for i ← 0 to n − 2
    minIndex ← i
    for j ← i + 1 to n − 1
      if array[j] < array[minIndex]: minIndex ← j
    swap array[i], array[minIndex]
06

When to use

When writes are expensive and reads are cheap: flash memory, EEPROM, or a list where moving an element is costly.
Small arrays where n − 1 swaps and a trivially simple loop matter more than the comparison count.
07

Pitfalls

Not adaptive: a sorted array costs exactly as much as a reversed one.
Not stable: the swap can jump an equal element over its twin.
Insertion sort does the same comparisons on average and far fewer on nearly sorted input; prefer it unless swaps are the bottleneck.
08

History

Selection sort is old enough to have no single inventor; it appears in the earliest sorting surveys of the 1950s as the obvious way to sort by hand. Its lasting niche is hardware with a limited number of writes, and it is the sort behind heap sort once the scan is replaced by a heap.

Back to Sorting