ITPEC FE Subject A April 2024 Question 7

N(N − 1) ÷ 2 swaps — in reverse order every pair of elements is out of order, and each bubble-sort swap fixes exactly one such pair.

Bubble sort swaps only adjacent elements that are out of order, and each swap removes exactly one inverted pair. In a reversed array all C(N, 2) pairs are inverted.

Pass by pass: (N − 1) + (N − 2) + … + 1 = N(N − 1) ÷ 2. For example, 4 3 2 1 needs 3 + 2 + 1 = 6 = 4 × 3 ÷ 2 swaps.

Answer (a)

Why not others:

• •(b) — N² ÷ 2 exceeds the true count by N ÷ 2, and for odd N is not even a whole number (4.5 for N = 3)
• •(c) — N(N − 1) counts each pair twice, once in each order
• •(d) — N² pairs every element with every element, itself included, and counts each pair twice

Key rule: Bubble sort makes exactly one swap per inversion (pair out of order), so its swap count equals the number of inversions in the input, from zero for sorted data upwards.

Algorithm and Programming · AI-written, may contain errors