Selection Sort
Scans the unsorted suffix for the minimum and swaps it to the front of that suffix.
- Comparisons 0
- Swaps 0
- sorted indices 0
- active
- compare
- swap
- sorted
Pseudocode
1 for i from 0 to n - 1
2 min = i
3 for j from i + 1 to n - 1
4 if a[j] < a[min]
5 min = j
6 swap a[i], a[min]
Step log
How it works, runtime and memory
Selection Sort conceptually splits the array into a sorted prefix (empty at first) and an unsorted suffix. Every round it scans the entire unsorted part, remembers the index of the smallest value and swaps that value to the front of the unsorted suffix at the end of the round. The sorted prefix grows by one. After n-1 rounds the entire array is sorted. The number of comparisons is always quadratic (roughly n^2/2), regardless of the input: best, average and worst case are all O(n^2). In return the algorithm performs at most n-1 swaps, minimising the number of writes. Selection Sort runs in-place (O(1) extra memory) but is not stable: a swap across a longer distance can move equal elements past each other.
Complexity
- Best case
O(n^2) - Average case
O(n^2) - Worst case
O(n^2) - Extra space
O(1)
When to use it
Useful when writes are expensive, for example on flash memory with limited write cycles. Selection Sort performs at most n - 1 actual swaps, whereas Bubble or Insertion Sort write to the array many more times.