Practice: Counting Swaps
Count the number of swaps needed to sort an array using bubble sort. This problem builds on your understanding of the bubble sort algorithm by tracking how many swap operations are performed.
Input
arr: a list of integers to be sorted
Output
An integer representing the total number of swaps performed during bubble sort
Examples
Example 1:
Input: arr = [1, 2, 3, 4, 5]
Output: 0
Explanation:
- The array is already sorted, so no swaps are needed
Example 2:
Input: arr = [5, 4, 3, 2, 1]
Output: 10
Explanation:
- This is the worst case (reverse sorted)
- Pass 1: 4 swaps (5 bubbles to end)
- Pass 2: 3 swaps (4 bubbles to position)
- Pass 3: 2 swaps (3 bubbles to position)
- Pass 4: 1 swap (2 bubbles to position)
- Total: 4 + 3 + 2 + 1 = 10 swaps
Example 3:
Input: arr = [3, 1, 4, 2]
Output: 3
Explanation:
- Pass 1: Compare and swap (3,1), (3,4) no swap, (4,2) → 2 swaps → [1, 3, 2, 4]
- Pass 2: (1,3) no swap, (3,2) swap → 1 swap → [1, 2, 3, 4]
- Total: 3 swaps