Minimum number of swaps required to minimize sum of absolute differences between adjacent array elements | C ++ program for the above approach ; Comparator to sort in the descending order ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool mycmp ( pair < int , int > a , pair < int , int > b ) { return a . first > b . first ; } int minSwapsAsc ( vector < int > arr , int n ) { pair < int , int > arrPos [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { arrPos [ i ] . first = arr [ i ] ; arrPos [ i ] . second = i ; } sort ( arrPos , arrPos + n ) ; vector < bool > vis ( n , false ) ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( vis [ i ] arrPos [ i ] . second == i ) continue ; int cycle_size = 0 ; int j = i ; while ( ! vis [ j ] ) { vis [ j ] = 1 ; j = arrPos [ j ] . second ; cycle_size ++ ; } if ( cycle_size > 0 ) { ans += ( cycle_size - 1 ) ; } } return ans ; } int minSwapsDes ( vector < int > arr , int n ) { pair < int , int > arrPos [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { arrPos [ i ] . first = arr [ i ] ; arrPos [ i ] . second = i ; } sort ( arrPos , arrPos + n , mycmp ) ; vector < bool > vis ( n , false ) ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( vis [ i ] arrPos [ i ] . second == i ) continue ; int cycle_size = 0 ; int j = i ; while ( ! vis [ j ] ) { vis [ j ] = 1 ; j = arrPos [ j ] . second ; cycle_size ++ ; } if ( cycle_size > 0 ) { ans += ( cycle_size - 1 ) ; } } return ans ; } int minimumSwaps ( vector < int > arr ) { int S1 = minSwapsAsc ( arr , arr . size ( ) ) ; int S2 = minSwapsDes ( arr , arr . size ( ) ) ; return min ( S1 , S2 ) ; } int main ( ) { vector < int > arr { 3 , 4 , 2 , 5 , 1 } ; cout << minimumSwaps ( arr ) ; return 0 ; }