python minimum swaps 2

Solutions on MaxInterview for python minimum swaps 2 by the best coders in the world

showing results for - "python minimum swaps 2"
Maël
24 Apr 2018
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