Minimum number of swaps required to sort an array | Function returns the minimum number of swaps required to sort the array ; Create two arrays and use as pairs where first array is element and second array is position of first element ; Sort the array by array element values to get right position of every element as the elements of second array . ; To keep track of visited elements . Initialize all elements as not visited or false . ; Initialize result ; Traverse array elements ; alreadt swapped or alreadt present at correct position ; find number of nodes in this cycle and add it to ans ; move to next node ; update answer by adding current cycle ; return answer ; Driver Code
def minSwaps ( arr ) : NEW_LINE INDENT n = len ( arr ) NEW_LINE arrpos = [ * enumerate ( arr ) ] NEW_LINE arrpos . sort ( key = lambda it : it [ 1 ] ) NEW_LINE vis = { k : False for k in range ( n ) } NEW_LINE ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if vis [ i ] or arrpos [ i ] [ 0 ] == i : NEW_LINE INDENT continue NEW_LINE DEDENT cycle_size = 0 NEW_LINE j = i NEW_LINE while not vis [ j ] : NEW_LINE INDENT vis [ j ] = True NEW_LINE j = arrpos [ j ] [ 0 ] NEW_LINE cycle_size += 1 NEW_LINE DEDENT if cycle_size > 0 : NEW_LINE INDENT ans += ( cycle_size - 1 ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT arr = [ 1 , 5 , 4 , 3 , 2 ] NEW_LINE print ( minSwaps ( arr ) ) NEW_LINE