Bubble, Insertion & Selection Sort
The three quadratic sorts GATE traces pass-by-pass — bubble bubbles, selection picks the min, insertion grows a sorted prefix. Know their passes, stability, and Big-O cold.
What you'll learn
- Bubble sort swaps adjacent out-of-order pairs; the largest element bubbles to the end each pass
- Selection sort swaps the minimum of the unsorted part into place: always Theta(n^2), at most n-1 swaps
- Insertion sort grows a sorted prefix and is O(n) on nearly-sorted input
- Stability: bubble and insertion are stable, selection is not
Before you start
Three classic sorts are all O(n²), yet GATE keeps testing them because each
moves elements by a different rule — and a single pass of one looks nothing
like a single pass of another. The exam shows you an array after k passes and
asks which algorithm produced it, or how many swaps it took. Win those marks by
knowing each algorithm’s per-pass fingerprint. The payoff is broader too: the
stability and in-place tradeoffs you meet here are exactly what you weigh when
picking a sort key in pandas or a database ORDER BY on real data.
The three rules
- Bubble sort — walk the array, swapping every adjacent pair that is out of order. Each full pass drags the largest remaining element to the end (it “bubbles up”). One element settles at the back per pass.
- Selection sort — find the minimum of the unsorted part and swap it into
the next front slot. One element settles at the front per pass, using at
most one swap. It always scans the whole unsorted region, so it is
Θ(n²)even on an already-sorted array. - Insertion sort — keep the left portion sorted; take each next element and
slide it left into its place. On nearly-sorted input each element barely
moves, giving a
O(n)best case.
Race them and watch the fingerprints: bubble and insertion freeze instantly on sorted input, while selection grinds through every comparison regardless.
| Algorithm | Comparisons (worst) | Swaps (worst) | Best case | Stable? |
|---|---|---|---|---|
| Bubble | O(n²) | O(n²) | O(n) — already sorted | Yes |
| Insertion | O(n²) | O(n²) | O(n) — nearly sorted | Yes |
| Selection | O(n²) | O(n) — at most n−1 | Θ(n²) — always scans fully | No |
How GATE asks this
The 2024 paper gave the array [4, 3, 2, 1, 5] and asked which of bubble,
insertion, selection sorts it into ascending order in exactly two passes — a
pure pass-tracing MCQ. The companion NAT style hands you a small array and asks
for the array state after k passes or the total number of swaps. Both
reward the same skill: simulate one algorithm’s passes faithfully without
confusing it with another’s.
Worked example — sorted in exactly two passes (2024)
Which of bubble, insertion, or selection sort sorts
[4, 3, 2, 1, 5]into ascending order in exactly two passes? Answer: selection sort only.
Selection — pass 1 finds the minimum 1 (at index 3) and swaps it to the
front; pass 2 finds the next minimum 2 and swaps it into place:
start: [4, 3, 2, 1, 5]
pass 1: min = 1 -> swap to front -> [1, 3, 2, 4, 5]
pass 2: min of rest = 2 -> in place -> [1, 2, 3, 4, 5] ✓ sortedBubble drags only the largest to the back each pass, so two passes is not enough on this reversed prefix:
start: [4, 3, 2, 1, 5]
pass 1: [3, 2, 1, 4, 5] (4 bubbled to the back)
pass 2: [2, 1, 3, 4, 5] still unsorted — 2, 1 out of orderInsertion grows a sorted prefix one slot per pass, so after two passes only the first three entries are ordered:
start: [4, 3, 2, 1, 5]
pass 1: [3, 4, 2, 1, 5] (sorted prefix [3,4])
pass 2: [2, 3, 4, 1, 5] still unsorted — 1 not yet insertedOnly selection finishes. The reason is structural: this input puts the two smallest values at the back, and selection is the only one of the three that reaches to the back to pull a minimum forward each pass.
Quick check
Quick check
Practice this in an interview
All questionsMaintain a min-heap of size k. Stream every element through: push it onto the heap, then if the heap exceeds size k, pop the minimum. After processing all elements, the heap's minimum is the kth largest — it is the smallest among the top-k values seen so far.
Even after rotation, one of the two halves around mid is always fully sorted. Check which half is sorted, then decide whether the target falls inside it. If yes, narrow to that half; if no, search the other. This keeps binary search's O(log n) guarantee.
Because the array is sorted, you can place one pointer at the start and one at the end, then squeeze them inward. If the sum is too big, move the right pointer left; if too small, move the left pointer right. This converges in one pass with O(1) extra space.
Maintain a second 'min stack' in parallel: every push also records the current minimum at that moment. When you pop the main stack, pop the min stack too. The top of the min stack is always the current minimum — no scanning needed.