Insertion sort: like sorting playing cards
Watch insertion sort take each number in turn and slide it left into its place among the numbers already sorted, the way you sort cards in your hand. Count its comparisons and swaps, and compare it with bubble sort and selection sort on a jumbled, a sorted and a reversed list.
Core concept
Insertion sort keeps a sorted part on the left and inserts the next number into it by sliding it past every bigger number; on a list that is nearly sorted it does very little work
Topic: Algorithms
Think of how you sort playing cards in your hand. You keep the cards on the left in order, pick up the next card, and slide it left past every card that is bigger until it fits. Insertion sort does the same with numbers. The first number on its own is already sorted. Then it takes the second number, the key, and compares it with the numbers on its left: while the one on the left is bigger, they swap places. When the number on the left is smaller, or there is nothing left, the key is in its place, and the sorted part has grown by one. On a list that is already sorted, each key needs only one comparison and no swaps, which makes insertion sort very quick for lists that are nearly in order.
What you will learn
- Describe how insertion sort inserts each number into the sorted part on the left.
- Trace the key as it slides left past bigger numbers.
- Count the comparisons and swaps insertion sort makes.
- Compare insertion sort with bubble sort and selection sort on the same list.
Before you start
- Know how bubble sort and selection sort put a list in order.
Materials
- A few playing cards, or paper slips with numbers
Equipment
- None
Procedure
- Run insertion sort on the jumbled list and read the comparisons and swaps.
- Step through it and watch each key slide left.
- Sort the sorted list and the reversed list, and compare the work with the other sorts.
- Answer the practice challenges.