Swaps in a bubble sort — Aptitude Question
Swaps in a bubble sort: How many swaps does bubble sort perform while sorting [5, 4, 3, 2, 1] into ascending order? Answer and worked solution on CodeKairo.
- Topic: Data Structures & Algorithms
- Section: Programming MCQs
- Difficulty: Medium
- Time target: 90 seconds
Question
How many swaps does bubble sort perform while sorting [5, 4, 3, 2, 1] into ascending order?
Options
- 4
- 5
- 10
- 20
Show the answer and the worked solution
Correct answer: C. 10
Worked solution
- Each swap in bubble sort exchanges two adjacent elements, removing exactly one inversion.
- The array is in exactly reverse order, so every pair of positions is an inversion.
- There are C(5, 2) = 10 such pairs, so bubble sort performs 10 swaps.
Answer: 10.
The idea
The swap count of any adjacent-exchange sort equals the number of inversions in the input. That is also why insertion sort runs in O(n + inversions) and is excellent on nearly sorted data.
Shortcut. On a reversed array every comparison finds the larger element in front, so the passes swap 4, 3, 2 and 1 times: 4 + 3 + 2 + 1 = 10.
Common trap. 4 counts only the swaps in the first pass, which carries 5 to the end; three more passes are still needed.
All Data Structures & Algorithms questions · placement mock tests