Selection Sort
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.
Check your understanding
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.
How it runs, step by step
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.
Write it yourself
Define selectionSort(values) and return the same values in ascending order. It runs in your browser against this lesson's own 5 examples.
// Find the smallest value in what is left, and swap it into place.function selectionSort(values) { return values;}
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.
Topics covered
Related
Where this is used
Standard librariesHeapsort, which is this algorithm with a faster search
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.
EmbeddedSorting on flash and EEPROM
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.
SearchTop-k without sorting the rest
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.
DatabasesBuilding the initial runs in an external sort
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.
Why it works this way
Making it stable costs the one thing it is good at
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.
Why the outer loop stops one short of the end
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.
What the min != i guard is really protecting
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.
Why a sorted array does not finish any faster
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.
Read more
- Selection sortWikipedia
- HeapsortWikipedia
- Cycle sort, the minimum-write sortWikipedia
- Selection algorithmWikipedia
- Tournament sort and replacement selectionWikipedia
Next up
- Counting SortCount occurrences of each key, prefix-sum the counts, place each element at its final index.
- Heap SortBuild a max-heap in place, then repeatedly swap the root to the end of the shrinking heap and sift the new root down.
- QuickselectPartition like quick sort, but only follow the side that holds the k-th value.