Insertion Sort vs Selection Sort
Insertion sort slides each item back into place. It is quick when the list is nearly in order. Selection sort looks for the smallest item on each pass. It is always slow.
Insertion Sort
Take each item in turn. Slide it back to its right place.
Insertion sort builds a sorted part one item at a time. It takes the next item and slides it back until it sits in the right spot. On a list that is already nearly sorted, it is very fast. On a big jumbled list it is slow, about n squared steps. Fast sorts often switch to it for very small pieces.
Selection Sort
Find the smallest item left. Move it to the front. Do it again and again.
Selection sort finds the smallest item left and swaps it to the front. Then it does the same for the rest of the list, one place at a time. It always takes about n squared steps, even if the list is already sorted. It makes very few swaps, at most one per place. That only helps when moving items costs a lot.
In one line
- Insertion Sort
- Take each item in turn. Slide it back to its right place.
- Selection Sort
- Find the smallest item left. Move it to the front. Do it again and again.