The number of swappings needed to sort the numbers 8, 22, 7, 9, 31, 5, 13 in…
2017
The number of swappings needed to sort the numbers 8, 22, 7, 9, 31, 5, 13 in ascending order, using bubble sort is
- A.
11
- B.
12
- C.
13
- D.
10
Attempted by 259 students.
Show answer & explanation
Correct answer: D
In bubble sort, the number of swaps required to sort an array is exactly equal to the total count of inversions in that array.
Given the array: [8, 22, 7, 9, 31, 5, 13]. An inversion is a pair (i, j) where i < j and A[i] > A[j].
Counting inversions for each element:
- 8 is greater than 7 and 5 (2 inversions).
- 22 is greater than 7, 9, 5, and 13 (4 inversions).
- 7 is greater than 5 (1 inversion).
- 9 is greater than 5 (1 inversion).
- 31 is greater than 5 and 13 (2 inversions).
Total inversions = 2 + 4 + 1 + 1 + 2 = 10. Therefore, 10 swaps are needed.