python minimum swaps 2
def minimumSwaps(arr):
'''
Finds minimum number of swaps necessary to sort array.
Ex. [3, 1, 2, 5, 4]
./\./\ ./\
3 1 2 5 4
\___/' \/'
Number of cycles = 2
Cycle 1 ( 3 -> 2 -> 1 -> 3 ):
- # hops = 3 ( 3 -> 2 | 2 -> 1 | 1 -> 3 )
- # swaps = # hops - 1 = 2
Cycle 2 ( 5 -> 4 -> 5 ):
- # hops = 2 ( 5 -> 4 | 4 -> 5 )
- # swaps = # hops - 1 = 1
Total swaps = 2 + 1 = 3
'''
swaps = 0
visited = set()
for n in arr:
# all nodes have been visited
if len(visited) == len(arr):
break
visited.add(n)
p = arr[n - 1] # item currently where n should be
# traverse swap cycle
while p != n and p not in visited:
visited.add(p)
swaps += 1
p = arr[p - 1]
return swaps