Minimum cost to sort an Array such that swapping X and Y costs XY | C ++ program for the above approach ; Function returns the minimum cost to sort the given array ; Create array of pairs in which 1 st element is the array element and 2 nd element is index of first ; Initialize the total cost ; Sort the array with respect to array value ; Initialize the overall minimum which is the 1 st element ; To keep track of visited elements create a visited array & initialize all elements as not visited ; Iterate over every element of the array ; If the element is visited or in the sorted position , and check for next element ; Create a vector which stores all elements of a cycle ; It covers all the elements of a cycle ; If cycle is found then the swapping is required ; Initialize local minimum with 1 st element of the vector as it contains the smallest element in the beginning ; Stores the cost with using only local minimum value . ; Stores the cost of using both local minimum and overall minimum ; Update the result2 ; Store the minimum of the two result to total cost ; Return the minimum cost ; Driver Code ; Given array arr [ ] ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minCost ( int arr [ ] , int n ) { pair < int , int > sorted [ n ] ; int total_cost = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sorted [ i ] . first = arr [ i ] ; sorted [ i ] . second = i ; } sort ( sorted , sorted + n ) ; int overall_minimum = sorted [ 0 ] . first ; bool vis [ n ] = { false } ; for ( int i = 0 ; i < n ; i ++ ) { if ( vis [ i ] && sorted [ i ] . second == i ) continue ; vector < int > v ; int j = i ; while ( ! vis [ j ] ) { vis [ j ] = true ; v . push_back ( sorted [ j ] . first ) ; j = sorted [ j ] . second ; } if ( v . size ( ) > 0 ) { int local_minimum = v [ 0 ] , result1 = 0 , result2 = 0 ; for ( int k = 1 ; k < v . size ( ) ; k ++ ) result1 += ( local_minimum * v [ k ] ) ; for ( int k = 0 ; k < v . size ( ) ; k ++ ) result2 += ( overall_minimum * v [ k ] ) ; result2 += ( overall_minimum * local_minimum ) ; total_cost += min ( result1 , result2 ) ; } } return total_cost ; } int main ( ) { int arr [ ] = { 1 , 8 , 9 , 7 , 6 } ; int n = ( sizeof ( arr ) / sizeof ( int ) ) ; cout << minCost ( arr , n ) ; return 0 ; }