Minimum number of swaps required to minimize sum of absolute differences between adjacent array elements | Function to find the minimum number of swaps required to sort the array in increasing order ; Stores the array elements with its index ; Sort the array in the increasing order ; Keeps the track of visited elements ; Stores the count of swaps required ; Traverse array elements ; If the element is already swapped or at correct position ; Find out the number of nodes in this cycle ; Update the value of j ; Move to the next element ; Increment cycle_size ; Update the ans by adding current cycle ; Function to find the minimum number of swaps required to sort the array in decreasing order ; Stores the array elements with its index ; Sort the array in the descending order ; Keeps track of visited elements ; Stores the count of resultant swap required ; Traverse array elements ; If the element is already swapped or at correct position ; Find out the number of node in this cycle ; Update the value of j ; Move to the next element ; Increment the cycle_size ; Update the ans by adding current cycle size ; Function to find minimum number of swaps required to minimize the sum of absolute difference of adjacent elements ; Sort in ascending order ; Sort in descending order ; Return the minimum value ; Drive Code
def minSwapsAsc ( arr , n ) : NEW_LINE INDENT arrPos = [ [ arr [ i ] , i ] for i in range ( n ) ] NEW_LINE arrPos = sorted ( arrPos ) NEW_LINE vis = [ False ] * ( n ) NEW_LINE ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( vis [ i ] or arrPos [ i ] [ 1 ] == 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 ] = 1 NEW_LINE j = arrPos [ j ] [ 1 ] 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 def minSwapsDes ( arr , n ) : NEW_LINE INDENT arrPos = [ [ 0 , 0 ] for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT arrPos [ i ] [ 0 ] = arr [ i ] NEW_LINE arrPos [ i ] [ 1 ] = i NEW_LINE DEDENT arrPos = sorted ( arrPos ) [ : : - 1 ] NEW_LINE vis = [ False ] * n NEW_LINE ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( vis [ i ] or arrPos [ i ] [ 1 ] == 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 ] = 1 NEW_LINE j = arrPos [ j ] [ 1 ] 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 def minimumSwaps ( arr ) : NEW_LINE INDENT S1 = minSwapsAsc ( arr , len ( arr ) ) NEW_LINE S2 = minSwapsDes ( arr , len ( arr ) ) NEW_LINE return min ( S1 , S2 ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 3 , 4 , 2 , 5 , 1 ] NEW_LINE print ( minimumSwaps ( arr ) ) NEW_LINE DEDENT