Bubble sort and selection sort: passes, comparisons, swaps

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Expected probes for an unsuccessful search, open addressing, α = 0.75? from Lesson 2.2.3
• Max probes of binary search on n elements? from Lesson 2.1.1
• Θ(n(n − 1)/2)? from Lesson 1.1.1

1 · The Hook

🎣

Sorting is the most-studied problem in computing, because so much else (binary search, duplicates, scheduling) becomes easy on sorted data. We start with two simple quadratic sorts. They are slow on big inputs, but GATE loves asking what the array looks like after k passes, and how many swaps were made.

2 · Predict First

🤔

Bubble sort makes passes over A = [5, 2, 9, 1, 7, 3], swapping each adjacent pair that is out of order. What does A look like after the first pass?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

5↔2, 9↔1, 9↔7, 9↔3 swap; 5 and 9 stay: [2, 5, 1, 7, 3, 9]. The largest element, 9, has "bubbled" to the end.

Bubble sort

for (i = 0; i < n - 1; i++) {          // pass i
    swapped = 0;
    for (j = 0; j < n - 1 - i; j++)
        if (A[j] > A[j + 1]) { swap(A[j], A[j + 1]); swapped = 1; }
    if (!swapped) break;               // already sorted
}

• After pass k, the k largest elements are in their final places at the end.
• Comparisons: (n − 1) + (n − 2) + … = n(n − 1)/2 in the worst case; with the early exit, a sorted array takes n − 1 comparisons (one pass, no swaps).
• Swaps = number of inversions (each swap of adjacent out-of-order elements removes exactly one inversion; Lesson 3.1.2 defines inversions).
• Worst Θ(n²), best Θ(n), in-place, stable.

Selection sort

for (i = 0; i < n - 1; i++) {
    m = i;
    for (j = i + 1; j < n; j++)
        if (A[j] < A[m]) m = j;
    swap(A[i], A[m]);                  // put the minimum in place
}

• Pass i finds the minimum of A[i..n−1] and swaps it into position i.
• Comparisons: always n(n − 1)/2, whatever the input (Θ(n²) best and worst).
• Swaps: at most n − 1: the fewest writes of any simple sort.
• In-place; not stable (a long-distance swap can jump over an equal key).

Traces on A = [5, 2, 9, 1, 7, 3]

Bubble sort: pass 4 makes no swap and stops: 5 + 4 + 3 + 2 = 14 comparisons, 8 swaps. Selection sort: 15 comparisons, 2 swaps (passes 2, 4 and 5 find the minimum already in place).

4 · Visual

Bubble sort pass 1 on [5, 2, 9, 1, 7, 3]

[5 2] 9 1 7 3  -> swap -> 2 5 9 1 7 3
 2 [5 9] 1 7 3 -> keep
 2 5 [9 1] 7 3 -> swap -> 2 5 1 9 7 3
 2 5 1 [9 7] 3 -> swap -> 2 5 1 7 9 3
 2 5 1 7 [9 3] -> swap -> 2 5 1 7 3 9      largest is now last

5 · Worked Examples

Example 1 Easy

How many comparisons does selection sort make on 10 elements?

Solution

10 × 9 / 2 = 45, regardless of order.

Example 2 Medium

Bubble sort with early exit on the already sorted array [10, 20, 30, 40, 50]: comparisons and swaps?

Solution

One pass: 4 comparisons, 0 swaps.

Example 3 GATE

Bubble sort on the reverse-sorted array [8, 7, 6, 5, 4, 3, 2, 1]: number of swaps?

Solution

Every pair is an inversion: 8 × 7 / 2 = 28 swaps.

6 · GATE Traps

⚠️

• Selection sort makes n(n − 1)/2 comparisons even on sorted input.
• Bubble sort's best case Θ(n) needs the early-exit check.
• Bubble swaps = inversions; selection swaps ≤ n − 1.
• Selection sort is not stable.

7 · Memory Hook

🧠

"Bubble pushes the biggest to the back; selection pulls the smallest to the front."

8 · Connect the Dots

Phase 2 searched sorted data; Phase 3 produces it. Next: insertion sort, the quadratic sort that is fast on nearly sorted data, plus the words stable and in-place.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markBubble pass

Bubble sort on [4, 6, 2, 8, 1]. Array after the first pass?

• (A) [2, 4, 6, 1, 8]
• (B) [1, 2, 4, 6, 8]
• (C) [4, 2, 6, 1, 8]
• (D) [4, 6, 2, 1, 8]

Q2NAT1 markSelection comparisons

Selection sort on 20 elements. Number of comparisons?

Numerical answer: ________

Q3NAT2 marksBubble swaps

Bubble sort on [3, 1, 4, 1, 5, 9, 2, 6]. Number of swaps?

Numerical answer: ________

Q4NAT2 marksSelection swaps

Selection sort (swap only when the minimum is not already in place) on [3, 1, 4, 1, 5, 9, 2, 6]. Number of swaps?

Numerical answer: ________

Q5MSQ2 marksProperties

Which are true?

• (A) Bubble sort with early exit is Θ(n) on sorted input.
• (B) Selection sort is stable.
• (C) Selection sort makes at most n − 1 swaps.
• (D) After k passes of bubble sort, the k largest elements are in their final positions.

10 · Rule Card

• Bubble: adjacent swaps; pass k fixes the k-th largest; comparisons ≤ n(n−1)/2; best n − 1 (early exit); swaps = inversions; stable, in-place.
• Selection: min of the rest into place; always n(n−1)/2 comparisons; ≤ n − 1 swaps; in-place, not stable.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

bubble sortpassearly exitselection sortcomparisons n(n − 1)/2swaps vs comparisons

12 · Answer Vault