GATE@Zeal Basic DSA Searching and Sorting (Q24)

Question

You have given an array A[] = {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}. An inversion in an array A is a pair of array indices (i, j) such that i < j and A[i] > A[j]. Assume the array index starts at $0$. What is the maximal number of inversions that the following program fragment can eliminate?

if (i < j && A[i] > A[j]) {
    temp = A[5];
    A[5] = A[10];
    A[10] = temp;
}

Comments

Good question. However, initialisation of i and j values are missing in the question.
Further, the answer depends upon whether the given code is under for loop or stand alone code.

---

Sir, although I have written the question as it is, I think the code is under a for loop and i = 0 and j = i + 1, because these types of questions are asked in GATE using the concepts of Combinatorics as well as Algorithms.

Answer 1

 the number of inversions eliminated depends on the elements at the two indices.When you swap two elements in a strictly decreasing array, the number of inversions eliminated depends on the specific values of the elements at the two indices being swapped. Since the array is strictly decreasing, swapping two elements will disrupt the order and eliminate some inversions, but the exact number depends on the relative values of the elements.