Given an input array I want to calculate the minimum number of swaps to sort the array. I thought that its equal to inversion count but its not as depicted below:
array [6,4,3]
output: 1, just swap 6 with 3. But the inversions are actually 3.
So given an input array is there an efficient algorithm to determine the minimum number of swaps. I know that selection sort has minimum number of swaps but I also know that it is not efficient.
You can use this method:
Say this is your input array: [4 6 1 8 2 7]
Then, in sorted array, positions of elements will be, respectively: 3 4 1 6 2 5
Create a visit array: [0 0 0 0 0 0]
Start with 1'st index in position array, mark it as visited, jump to the position it represents, until the value of visit in visit[] is set.
Then, once a cycle is complete, chose the next element whose visit value is unset.
For a cycle of k elements, add k-1 to the swap counter.
Step by step in this example will be:
visiting index in position[] visit[]
position[1] = 3 [1 0 0 0 0 0]
position[3] = 1 [1 0 1 0 0 0]
Now, a cycle is formed. Since this cycle has 2 elements, add 1 to swap counter. Now we start with index 2.
position[2] = 4 [1 1 1 0 0 0]
position[4] = 6 [1 1 1 1 0 0]
position[6] = 5 [1 1 1 1 0 1]
position[5] = 2 [1 1 1 1 1 1]
Since visit[2] is set, a cycle is formed. This cycle has 4 elements, so, add 3 to swap counter.
See which next index in visit is still unset. (None). Stop here.
So, your answer is 1 + 3 = 4
