ITPEC FE Morning April 2022 Question 10

9 — every bubble sort exchange swaps one adjacent out-of-order pair, so the count equals the number of inversions.

Count, for each number, the smaller numbers to its right:

• •9: 2, 3, 0 → 3
• •2: 0 → 1
• •13: 3, 0 → 2
• •21: 3, 0 → 2
• •3: 0 → 1

Total: 3 + 1 + 2 + 2 + 1 = 9. Pass by pass the exchanges are 3, 2, 2, 1 and 1, ending with 0, 2, 3, 9, 13, 21.

Answer (c)

Why not others:

• •(a) 7 — the total after only three passes, leaving 2, 3, 0 still out of order
• •(b) 8 — the total after four passes; the fifth pass still has to swap 2 and 0
• •(d) 10 — more exchanges than inversions, which is impossible: each exchange removes exactly one inversion

Key rule: The number of exchanges in bubble sort equals the number of inversions, pairs where a larger value stands before a smaller one.

Algorithm and Programming · AI-written, may contain errors