Consider the array {1,5,4,3,2,6,7}. In this, the number of inversions is 6. But, actually, we need only 2 swaps to get the array totally sorted i.e., (5,2), (4,3). Can someone explain this situation? Am I understanding the meaning of inversions of array in the wrong sense or is there some intricacy which I am missing. Help would be very much appreciated. Thanks in advance.
If you consider swapping only adjacent elements then you have to do 6 swaps to get your array in sorted order.
1 Like
Can someone help me with this please?
Actually the definition of inversions has nothing to do with swapping. An inversion is a pair of indices (i,j), where i < j and a[i] > a[j]. So in your array we have the six inversions (1,2), (1,3), (1,4), (2,3), (2, 4), and (3, 4).
There is an alterative interpretation as the number of adjacent swaps. But hruday968 already mentioned that.
1 Like
Which condition does the concept “Inversions in an array” refer to ? Is it “swapping only adjacent elements” or “swapping any 2 elements” ??
“swap adjacent elements”
1 Like
Thank you so much.
Thanks a lot.!