Selection sort

O(n²)

Selection sort splits the array into a sorted front and an unsorted rest. Each round it scans the unsorted part to find the minimum and swaps it to the boundary. It always does the same number of comparisons — O(n²) — but very few swaps (at most n−1), which matters when writes are expensive.

Array
Edit the input and press Play

How it works

  1. Scan the unsorted region to find its smallest value.
  2. Swap that value with the first unsorted slot.
  3. The sorted region at the front grows by one.
  4. Repeat until the whole array is sorted.

Pseudocode

1selectionSort(a):                   # O(n²)2  for i from 0 to n-1:3    min ← i4    for j from i+1 to n-1:5      if a[j] < a[min]: min ← j      # find the smallest left6    swap(a[i], a[min])               # put it at the front