ITPEC FE Morning April 2022 Question 10
ITPEC FE Morning April 2022 — Question 10 of 80
Bubble Sort Exchange Count — equals the number of inversions in the array.
Given: 9, 2, 13, 21, 3, 0
An inversion is a pair (i, j) where i < j but arr[i] > arr[j]. Count how many smaller elements exist to the right of each element:
- •
9: smaller to the right →2, 3, 0→ 3 - •
2: smaller to the right →0→ 1 - •
13: smaller to the right →3, 0→ 2 - •
21: smaller to the right →3, 0→ 2 - •
3: smaller to the right →0→ 1 - •
0: none → 0
Total inversions = 3 + 1 + 2 + 2 + 1 + 0 = 9
Why not others:
- (a) 7 — undercounts inversions
- (b) 8 — common mistake from mistracking pass boundaries
- (d) 10 — overcounts by adding a non-existent pair
Key rule: Bubble sort swap count = total inversions. For each element, count how many smaller elements appear to its right. Sum them up.
AI-generated — may contain errors
The original exam layout is preserved in the image so diagrams, formulas, tables, and code remain accurate.
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.