python minimum swaps 2 code example

Example: 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