Suppose that insertion sort is applied to the array \([1, 3, 5, 7, 9, 11, x, 15, 13]\) and it takes exactly two swaps to sort the array. Select all possible values of \(x\).
Answer
(A), (C)
Explanation
Each swap in insertion sort exchanges two adjacent elements that are out of order, removing exactly one inversion. So the number of swaps equals the number of inversions.
Without \(x\), the only inversion is the pair (15, 13), so \(x\) must add exactly one more:
- \(x = 10\): only 11, placed before it, is larger. Total 2.
- \(x = 12\): no element is out of order with it. Total 1.
- \(x = 14\): only 13, placed after it, is smaller. Total 2.
- \(x = 16\): both 15 and 13, placed after it, are smaller. Total 3.
Answer: A, C