Selection sort
Finds the smallest remaining value and swaps it into the next place. It makes very few swaps, but always the same number of comparisons.
- Ω(n²)
- Θ(n²)
- O(n²)
- O(1)
- no
- yes
Best case: how the time grows with the list size n when the input is the easiest for this algorithm.
Average: the usual growth of time with n. n² means twice as many values take about four times as long; n log n grows much more slowly.
Worst case: the growth on the hardest input. Useful when speed must never drop.
Space: how much extra memory is needed besides the list. 1 means a few variables, n means a copy of the list.
Stable: two equal values keep their original order. Matters when sorting by one field of a record.
In place: sorts inside the list itself, with no second list.
- comparing
- moving
- current minimum
- in final place
Try this: Pick a reversed list. The number of comparisons stays exactly the same as for any other list.
How it works
Look through the unsorted part and find the smallest value. Swap it with the first unsorted value, so one more value is in its final place. It always checks every remaining value, even when the list is already sorted.
When it is a good choice
Useful when moving data is expensive but reading it is cheap, because it swaps at most once per position. In most other cases insertion sort is the better simple choice.