2.1Elementary sorts: bubble, insertion, selection
The idea
Bubble, insertion and selection sort are the simple quadratic sorts. They differ in how many comparisons and swaps they make.
Think of it like this: Sorting a hand of cards: insertion slides each new card into place; selection repeatedly picks the smallest card.
Why it exists
Counting comparisons and swaps on a small array is a very common question.
How it works
- Bubble: swap neighbours that are out of order, repeat passes.
- Insertion: shift larger elements right, drop the key in the gap.
- Selection: find the minimum, swap it to the front.
- Insertion-sort shifts = number of inversions.
Worked example: Insertion sort on 5 2 9 1 7 3 8
Inversions: 9. Insertion sort makes exactly 9 shifts. Selection sort makes at most 6 swaps for 7 elements.
Now play with it
- →Run insertion on the reversed array: n(n − 1)/2 shifts.
- →Run it on the sorted array: only n − 1 comparisons.
- Start: 5 2 9 1 7 3 8
- take key = 2
- 5 > 2: shift right
- insert 2 at position 0
- take key = 9
- 5 ≤ 9: stop
- insert 9 at position 2
- take key = 1
- 9 > 1: shift right
- 5 > 1: shift right
- 2 > 1: shift right
- insert 1 at position 0
- take key = 7
- 9 > 7: shift right
- 5 ≤ 7: stop
- insert 7 at position 3
- take key = 3
- 9 > 3: shift right
- 7 > 3: shift right
- 5 > 3: shift right
- 2 ≤ 3: stop
- insert 3 at position 2
- take key = 8
- 9 > 8: shift right
- 7 ≤ 8: stop
- insert 8 at position 5
Swaps (shifts) equal the number of inversions. Best case n − 1 comparisons on sorted input, worst n(n − 1)/2. Stable.
Check yourself
The number of element shifts made by insertion sort equals
Exam notes (the dense version)
Bubble: repeatedly swap adjacent out-of-order pairs; Θ(n²) comparisons (best case n − 1 with an early-exit flag). Insertion: insert each element into the sorted prefix; best O(n), worst O(n²), and the number of shifts equals the number of inversions. Selection: pick the minimum each pass; always n(n − 1)/2 comparisons but only n − 1 swaps. Bubble and insertion are stable; selection is not.
Previous year questions: Sorting & Searching (9)
PYQs are grouped by topic, so this is the full set for Sorting & Searching; try the ones that match this subtopic. Open all 9 on the topic page.