Selection Sort
Repeatedly find the smallest remaining element and move it into place, simple to write but slow on large lists.
Selection Sort Practice Problems
Easy
2 problemsMedium
2 problemsHard
1 problemsHow to practise selection sort
Spotting one
There is one specific reason to choose this. You want to write as little as possible. Selection sort makes at most one swap per position, the fewest of any simple sorting method.
If writing is expensive, because storage wears out or things have to be physically moved, this is the method that keeps it to a minimum.
The idea, plainly
Look through everything not yet sorted, find the smallest, swap it into the next position. Repeat.
It always does the same amount of looking, whatever the input. Already sorted data takes exactly as long as random data, which is unusual and worth noticing.
Where to start
Implement Selection Sort first.
Kth Smallest Element next, which shows what this method is actually good for. You do not need to sort everything to find the fifth smallest. Run five passes and stop. Stopping early is free here in a way it is not for most sorting methods.
Sort an Array Minimizing Swaps makes the low write count the actual goal.
Sort Employees by Rating just flips the comparison to sort largest first. Sort Intervals by Start is the interesting one, because plain selection sort does not keep equal items in their original order and this problem asks you to fix that. The fix is in how you move items, not how you find them.
Common mistakes
Swapping the moment you see something smaller instead of finishing the scan and swapping once. That turns it into a much slower method and throws away its only advantage.
Assuming equal items keep their order. They do not, unless you deliberately change the movement step.
Expecting it to finish early on sorted input. It cannot tell, and it will not.
Related concepts
| Topic | Description |
|---|---|
| Bubble Sort | Repeatedly swap neighboring out-of-order elements until the whole list is sorted, simple but slow on large lists. |
| Merge Sort | Split the list in half, sort each half, then merge them back together in order, giving reliable O(n log n) time. |
| Quick Sort | Pick a pivot, move smaller elements left and larger ones right, then repeat on each side to sort in place. |
| Insertion Sort | Build the sorted list one element at a time, inserting each new element into its correct position as you go. |
| Heap Sort | Build a heap from the list, then repeatedly pull out the largest element to sort in place in O(n log n). |
| Counting Sort | Count how many times each value appears, then rebuild the list in order, sorting in O(n) when values fall in a small range. |