Bubble, Insertion & Selection Sort

The last lesson left binary search demanding a sorted array — so this lesson supplies one. 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. You 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 almost instantly on sorted input, while selection grinds through every comparison regardless — a difference you can see before you can prove.

The single table above answers most “which sort” and “what does it cost” questions — but only if you can also produce the passes by hand. Here are the passes spelled out:

def selection_passes(a):
    a = a[:]
    n = len(a)
    snaps = [a[:]]
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]      # min of unsorted part to the front
        snaps.append(a[:])
    return snaps

def bubble_passes(a):
    a = a[:]
    n = len(a)
    snaps = [a[:]]
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
        snaps.append(a[:])
    return snaps

start = [4, 3, 2, 1, 5]
sel = selection_passes(start)
bub = bubble_passes(start)
print("selection after pass 1:", sel[1])
print("selection after pass 2:", sel[2])
print("bubble    after pass 2:", bub[2])

prints:

selection after pass 1: [1, 3, 2, 4, 5]
selection after pass 2: [1, 2, 3, 4, 5]
bubble    after pass 2: [2, 1, 3, 4, 5]

Selection has the array fully sorted after two passes; bubble, on the same input, is still unsorted after two. That difference is the whole of the 2024 question below.

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]   ✓ sorted

Bubble 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 order

Insertion 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 inserted

Only 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.

A question to carry forward

For all their differences, these three share one ceiling: O(n²). On a small array that is fine, but on a million items n² is a trillion operations — simply unusable. And yet the complexity lesson promised a faster tier, O(n log n), and even named merge sort as living there. So a real question hangs over the quadratic sorts: how do you break through the n² wall? Here is the thread onward: what single strategic idea — split the problem, solve the pieces, combine the results — lets a sort run in O(n log n), and how do merge sort and quicksort each put it to work?

In one breath

• Three O(n²) sorts, each with a distinct per-pass fingerprint: bubble = largest bubbles to the back; selection = min swapped to the front; insertion = grow a sorted prefix.
• Best case: insertion O(n) (nearly sorted), bubble O(n) (with a no-swap check), selection Θ(n²) always (it scans fully regardless of order).
• Swaps: selection makes at most n−1 (O(n)); bubble/insertion make O(n²) worst case.
• Stable: bubble and insertion yes; selection no (its long swap can jump equal keys).
• GATE traces passes: on [4,3,2,1,5], only selection is sorted after exactly two passes (the 2024 question).

Practice