Question

Problem 3 . Suppose elements a[i] and a[i+k] are in the wrong order and we swap them. Prove that this will remove at least 1 inversion but at most 2k − 1 inversions. (This is textbook problem 7.3.) Further explain why both the lower bound of 1 and the upper bound of 2k − 1 can be attained for any i, k, where k > 0.

Answer 1

The inversion that existed between A[i]A[i] and A[i+k]A[i+k] is removed. This shows at least one inversion is removed. Now let's consider A[i],A[i+1],…,A[i+k−1],A[i+k]A[i],A[i+1],…,A[i+k−1],A[i+k], Suppose A[i]A[i] is greater than A[i+1],…,A[i+k]A[i+1],…,A[i+k] and A[i+k]A[i+k] is smaller than A[i],…,A[i+k−1]A[i],…,A[i+k−1]. In this case, by swapping A[i]A[i] and A[i+k]A[i+k], we fix 2k−12k−1 inversions (−1−1 is that A[i]A[i] greater than A[i+k]A[i+k] and A[i+k]A[i+k] smaller than A[i]A[i] points to the same inversion).

Another way to think about 2k−12k−1 is that for each of the k−1k−1 elements A[i+1],A[i+2],…,A[i+k−1]A[i+1],A[i+2],…,A[i+k−1], at most two inversions can be removed by exchange. For instance, for A[i+1]A[i+1], two inversions are A[i]A[i] and A[i+1]A[i+1], and A[i+1]A[i+1] and A[i+k]A[i+k] (i.e. for sequence 10,4,3, by swapping 10 and 3, we remove inversion {10,4} and {4,3}). Thus, a maximum of 2(k−1)+1=2k−12(k−1)+1=2k−1.