Minimum number of swaps required to sort an array | C ++ program to find minimum number of swaps required to sort an array ; Return the minimum number of swaps required to sort the array ; Hashmap which stores the indexes of the input array ; This is checking whether the current element is at the right place or not ; If not , swap this element with the index of the element which should come here ; Update the indexes in the hashmap accordingly ; Driver class ; Driver program to test the above function ; Output will be 5
#include <bits/stdc++.h> NEW_LINE using namespace std ; void swap ( vector < int > & arr , int i , int j ) { int temp = arr [ i ] ; arr [ i ] = arr [ j ] ; arr [ j ] = temp ; } int minSwaps ( vector < int > arr , int N ) { int ans = 0 ; vector < int > temp = arr ; map < int , int > h ; sort ( temp . begin ( ) , temp . end ( ) ) ; for ( int i = 0 ; i < N ; i ++ ) { h [ arr [ i ] ] = i ; } for ( int i = 0 ; i < N ; i ++ ) { if ( arr [ i ] != temp [ i ] ) { ans ++ ; int init = arr [ i ] ; swap ( arr , i , h [ temp [ i ] ] ) ; h [ init ] = h [ temp [ i ] ] ; h [ temp [ i ] ] = i ; } } return ans ; } int main ( ) { vector < int > a = { 101 , 758 , 315 , 730 , 472 , 619 , 460 , 479 } ; int n = a . size ( ) ; cout << minSwaps ( a , n ) ; }