Minimum number of swaps required to sort an array | C ++ program to find minimum number of swaps required to sort an array ; swap function ; indexOf function ; Return the minimum number of swaps required to sort the array ; This is checking whether the current element is at the right place or not ; Swap the current element with the right index so that arr [ 0 ] to arr [ i ] is sorted ; Driver Code ; 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 indexOf ( vector < int > & arr , int ele ) { for ( int i = 0 ; i < arr . size ( ) ; i ++ ) { if ( arr [ i ] == ele ) { return i ; } } return -1 ; } int minSwaps ( vector < int > arr , int N ) { int ans = 0 ; vector < int > temp ( arr . begin ( ) , arr . end ( ) ) ; sort ( temp . begin ( ) , temp . end ( ) ) ; for ( int i = 0 ; i < N ; i ++ ) { if ( arr [ i ] != temp [ i ] ) { ans ++ ; swap ( arr , i , indexOf ( arr , temp [ i ] ) ) ; } } return ans ; } int main ( ) { vector < int > a = { 101 , 758 , 315 , 730 , 472 , 619 , 460 , 479 } ; int n = a . size ( ) ; cout << minSwaps ( a , n ) ; }