Remember
- Always n(n-1)/2 comparisons, no matter the input.
- At most n-1 swaps, fewer than any other simple sort.
- Not stable, because a swap can throw an equal value past its twin.
Find the smallest value that is left. Swap it to the front. Repeat with the rest.
Sort 7 values. Each pass finds the smallest remaining value and moves it to the front.
The player pauses before each decision in this run and asks what happens next. Here are all 21, with their answers.
Current minimum is 5. Next value is 1. What happens?
Answer: New minimum. 1 < 5, so it becomes the minimum.
Current minimum is 1. Next value is 4. What happens?
Answer: Keep minimum. 4 >= 1, so the minimum is unchanged.
Current minimum is 1. Next value is 2. What happens?
Answer: Keep minimum. 2 >= 1, so the minimum is unchanged.
Current minimum is 1. Next value is 8. What happens?
Answer: Keep minimum. 8 >= 1, so the minimum is unchanged.
Current minimum is 1. Next value is 3. What happens?
Answer: Keep minimum. 3 >= 1, so the minimum is unchanged.
Current minimum is 1. Next value is 7. What happens?
Answer: Keep minimum. 7 >= 1, so the minimum is unchanged.
Current minimum is 5. Next value is 4. What happens?
Answer: New minimum. 4 < 5, so it becomes the minimum.
Current minimum is 4. Next value is 2. What happens?
Answer: New minimum. 2 < 4, so it becomes the minimum.
Current minimum is 2. Next value is 8. What happens?
Answer: Keep minimum. 8 >= 2, so the minimum is unchanged.
Current minimum is 2. Next value is 3. What happens?
Answer: Keep minimum. 3 >= 2, so the minimum is unchanged.
Current minimum is 2. Next value is 7. What happens?
Answer: Keep minimum. 7 >= 2, so the minimum is unchanged.
Current minimum is 4. Next value is 5. What happens?
Answer: Keep minimum. 5 >= 4, so the minimum is unchanged.
Current minimum is 4. Next value is 8. What happens?
Answer: Keep minimum. 8 >= 4, so the minimum is unchanged.
Current minimum is 4. Next value is 3. What happens?
Answer: New minimum. 3 < 4, so it becomes the minimum.
Current minimum is 3. Next value is 7. What happens?
Answer: Keep minimum. 7 >= 3, so the minimum is unchanged.
Current minimum is 5. Next value is 8. What happens?
Answer: Keep minimum. 8 >= 5, so the minimum is unchanged.
Current minimum is 5. Next value is 4. What happens?
Answer: New minimum. 4 < 5, so it becomes the minimum.
Current minimum is 4. Next value is 7. What happens?
Answer: Keep minimum. 7 >= 4, so the minimum is unchanged.
Current minimum is 8. Next value is 5. What happens?
Answer: New minimum. 5 < 8, so it becomes the minimum.
Current minimum is 5. Next value is 7. What happens?
Answer: Keep minimum. 7 >= 5, so the minimum is unchanged.
Current minimum is 8. Next value is 7. What happens?
Answer: New minimum. 7 < 8, so it becomes the minimum.
Sort 7 values. Each pass finds the smallest remaining value and moves it to the front.
Selection sort on 5, 1, 4, 2, 8, 3, 7. Each pass scans the unsorted part for its minimum and swaps it into place.
Pass 1: assume 5 at index 0 is the minimum, then scan the rest.
Pass 1. Current minimum is 5 at index 0. Scanning indices 1 to 6.
1 is smaller than 5: new minimum.
Comparing 1 at index 1 with the current minimum 5. 1 is smaller and becomes the new minimum.
4 is not smaller than 1: keep the minimum.
Comparing 4 at index 2 with the current minimum 1. The minimum stays 1.
2 is not smaller than 1: keep the minimum.
Comparing 2 at index 3 with the current minimum 1. The minimum stays 1.
8 is not smaller than 1: keep the minimum.
Comparing 8 at index 4 with the current minimum 1. The minimum stays 1.
3 is not smaller than 1: keep the minimum.
Comparing 3 at index 5 with the current minimum 1. The minimum stays 1.
7 is not smaller than 1: keep the minimum.
Comparing 7 at index 6 with the current minimum 1. The minimum stays 1.
Swap 1 into index 0. The sorted prefix grows.
Swapping 1 from index 1 with 5 at index 0. Indices 0 to 0 are sorted.
Pass 2: assume 5 at index 1 is the minimum, then scan the rest.
Pass 2. Current minimum is 5 at index 1. Scanning indices 2 to 6.
4 is smaller than 5: new minimum.
Comparing 4 at index 2 with the current minimum 5. 4 is smaller and becomes the new minimum.
2 is smaller than 4: new minimum.
Comparing 2 at index 3 with the current minimum 4. 2 is smaller and becomes the new minimum.
8 is not smaller than 2: keep the minimum.
Comparing 8 at index 4 with the current minimum 2. The minimum stays 2.
3 is not smaller than 2: keep the minimum.
Comparing 3 at index 5 with the current minimum 2. The minimum stays 2.
7 is not smaller than 2: keep the minimum.
Comparing 7 at index 6 with the current minimum 2. The minimum stays 2.
Swap 2 into index 1. The sorted prefix grows.
Swapping 2 from index 3 with 5 at index 1. Indices 0 to 1 are sorted.
Pass 3: assume 4 at index 2 is the minimum, then scan the rest.
Pass 3. Current minimum is 4 at index 2. Scanning indices 3 to 6.
5 is not smaller than 4: keep the minimum.
Comparing 5 at index 3 with the current minimum 4. The minimum stays 4.
8 is not smaller than 4: keep the minimum.
Comparing 8 at index 4 with the current minimum 4. The minimum stays 4.
3 is smaller than 4: new minimum.
Comparing 3 at index 5 with the current minimum 4. 3 is smaller and becomes the new minimum.
7 is not smaller than 3: keep the minimum.
Comparing 7 at index 6 with the current minimum 3. The minimum stays 3.
Swap 3 into index 2. The sorted prefix grows.
Swapping 3 from index 5 with 4 at index 2. Indices 0 to 2 are sorted.
Pass 4: assume 5 at index 3 is the minimum, then scan the rest.
Pass 4. Current minimum is 5 at index 3. Scanning indices 4 to 6.
8 is not smaller than 5: keep the minimum.
Comparing 8 at index 4 with the current minimum 5. The minimum stays 5.
4 is smaller than 5: new minimum.
Comparing 4 at index 5 with the current minimum 5. 4 is smaller and becomes the new minimum.
7 is not smaller than 4: keep the minimum.
Comparing 7 at index 6 with the current minimum 4. The minimum stays 4.
Swap 4 into index 3. The sorted prefix grows.
Swapping 4 from index 5 with 5 at index 3. Indices 0 to 3 are sorted.
Pass 5: assume 8 at index 4 is the minimum, then scan the rest.
Pass 5. Current minimum is 8 at index 4. Scanning indices 5 to 6.
5 is smaller than 8: new minimum.
Comparing 5 at index 5 with the current minimum 8. 5 is smaller and becomes the new minimum.
7 is not smaller than 5: keep the minimum.
Comparing 7 at index 6 with the current minimum 5. The minimum stays 5.
Swap 5 into index 4. The sorted prefix grows.
Swapping 5 from index 5 with 8 at index 4. Indices 0 to 4 are sorted.
Pass 6: assume 8 at index 5 is the minimum, then scan the rest.
Pass 6. Current minimum is 8 at index 5. Scanning indices 6 to 6.
7 is smaller than 8: new minimum.
Comparing 7 at index 6 with the current minimum 8. 7 is smaller and becomes the new minimum.
Swap 7 into index 5. The sorted prefix grows.
Swapping 7 from index 6 with 8 at index 5. Indices 0 to 5 are sorted.
Sorted. 21 comparisons and 6 swaps.
Result: the array is sorted in ascending order after 21 comparisons and 6 swaps.
def selection_sort(a):
for i in range(len(a) - 1):
min = i
for j in range(i + 1, len(a)):
if a[j] < a[min]:
min = j
if min != i:
swap(a, i, min)function selectionSort(a) {
for (let i = 0; i < a.length - 1; i++) {
let min = i;
for (let j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) min = j;
}
if (min !== i) swap(a, i, min);
}
}fun selectionSort(a: IntArray) {
for (i in 0 until a.size - 1) {
var min = i
for (j in i + 1 until a.size) {
if (a[j] < a[min]) min = j
}
if (min != i) swap(a, i, min)
}
}Define selectionSort(values) and return the same values in ascending order. It runs in your browser against this lesson's own 5 examples.
Heapsort keeps the same outer structure, repeatedly take the largest value that is left and put it at the end, and replaces the linear scan with a heap pop, so each selection costs O(log n) instead of O(n). That single substitution is the whole distance between O(n^2) and O(n log n). It matters in practice because introsort, the std::sort in libstdc++ and libc++, falls back to heapsort once quicksort's recursion gets too deep, which is what gives the standard sort its worst-case guarantee.
A flash or EEPROM cell survives a bounded number of erase and write cycles, so on that hardware a write is not just slow, it consumes the part. Selection sort reads O(n^2) times but performs at most n-1 swaps, and since a swap is two writes that is at most 2(n-1) writes to the array, which is the trade the hardware wants. Cycle sort pushes the same idea to its limit by writing each element at most once, about half as many writes again, at the cost of more comparisons still.
Stopping after k passes leaves the k smallest values in their final positions and the remaining n-k untouched, which is exactly what a search ranker or a leaderboard needs. Real implementations keep this early-stopping shape and swap the selection step for a heap: C++ partial_sort, Python heapq.nsmallest and Lucene's top-docs collector all produce the k smallest in order without ever ordering the rest. The saving is real because k is usually 10 or 100 against an n of millions.
When the data does not fit in memory, a sort-merge first writes out sorted runs and then merges them, and the fewer runs there are the fewer merge passes are needed. Replacement selection fills memory, then repeatedly emits the smallest record that is still no less than the last one written, refilling the vacated slot from the input, with a tournament tree doing the selection in O(log n). Because incoming records often still qualify for the current run, the runs come out about twice the size of memory instead of exactly one memory's worth.
The usual fix is to stop swapping: shift the block from i up to min - 1 one slot to the right and drop the minimum into a[i], so equal values keep the order they arrived in. That turns at most n-1 swaps into up to n(n-1)/2 writes, which throws away the exact property selection sort was chosen for. When you need both stability and few writes, sort pairs of value and original index instead and break ties on the index.
After n-1 passes every slot but the last is settled, and the single value left has nowhere else to go, so a final pass would scan a one-element range and swap it with itself. That is why the bound is a.size - 1. The same expression is a live hazard in C and C++, where size() and sizeof-based counts are unsigned, so size() - 1 on an empty container wraps to a huge number and the loop walks off the array. Rust is safer about it rather than immune: len() - 1 on an empty slice underflows usize, which panics in a debug build and wraps in a release build, where the bounds check on the index then panics instead of reading out of bounds. Kotlin's 0 until -1 is simply empty, so the code here survives an empty array by accident rather than by design.
Skipping the swap when the minimum is already in place saves two writes, and on nearly sorted input that is most of the writes the algorithm would have done. It also protects correctness if the swap is written as the XOR trick, because a[i] ^= a[min] with i equal to min zeroes the element instead of leaving it alone. Some implementations drop the guard on the grounds that a mispredicted branch costs more than a redundant store. Keep it whenever a write is expensive, which is the situation selection sort is usually picked for.
The invariant only promises that the prefix is final. It says nothing about the suffix, and the smallest value in the suffix cannot be known until every element of it has been looked at. Bubble sort and insertion sort compare neighbours, so a pair that is already in order is evidence of order they can act on: bubble sort stops once a whole pass makes no swap, and insertion sort's inner loop exits on the first element that is already smaller. Selection sort never collects evidence of that kind. A fixed comparison count still does not make it constant-time in the cryptographic sense: the comparison branches on the data and the swap may or may not happen, so the running time leaks a little about the input.
Dynamic Array