1def minimumSwaps(arr):
2 '''
3 Finds minimum number of swaps necessary to sort array.
4
5 Ex. [3, 1, 2, 5, 4]
6
7 ./\./\ ./\
8 3 1 2 5 4
9 \___/' \/'
10
11 Number of cycles = 2
12
13 Cycle 1 ( 3 -> 2 -> 1 -> 3 ):
14 - # hops = 3 ( 3 -> 2 | 2 -> 1 | 1 -> 3 )
15 - # swaps = # hops - 1 = 2
16
17 Cycle 2 ( 5 -> 4 -> 5 ):
18 - # hops = 2 ( 5 -> 4 | 4 -> 5 )
19 - # swaps = # hops - 1 = 1
20
21 Total swaps = 2 + 1 = 3
22 '''
23
24 swaps = 0
25 visited = set()
26
27 for n in arr:
28
29 # all nodes have been visited
30 if len(visited) == len(arr):
31 break
32
33 visited.add(n)
34 p = arr[n - 1] # item currently where n should be
35
36 # traverse swap cycle
37 while p != n and p not in visited:
38 visited.add(p)
39 swaps += 1
40 p = arr[p - 1]
41
42 return swaps