An inversion in an array $a$ is a pair of array indices $(i, j)$ such that $i<j$ but $a[i]>a[j]$.
What is the maximum number of inversions that can be eliminated by the following program fragment?
tmp = a[5] ; a[5] = a[10] ; a[10]= tmp ;
$ \large{\colorbox{yellow}{Detailed video solution of this question with direct time stamp}}$ All India Mock Test 2 - Solutions Part 2
sample eg, as mentioned in ans 21|15|13|12|11|10 so, worst case(max inversions scenario):-EVERY inner ele (ie a[6] – a[9]) have inversions with both border elements(a[5],a[10]) and also within themselves too Now, if border ele are swapped then, no inner ele has inversions with border elements, then per inner element, 2 inversions decreases, and 1 more inversion decrease(between the border elements so 2*4 +1=9
64.3k questions
77.9k answers
244k comments
80.0k users