Minimum number of swaps required to sort an array | Java program to find minimum number of swaps required to sort an array ; Function returns the minimum number of swaps required to sort the array ; Create two arrays and use as pairs where first array is element and second array is position of first element ; Sort the array by array element values to get right position of every element as the elements of second array . ; To keep track of visited elements . Initialize all elements as not visited or false . ; Initialize result ; Traverse array elements ; already swapped and corrected or already present at correct pos ; find out the number of node in this cycle and add in ans ; move to next node ; Update answer by adding current cycle . ; Return result ; Driver class ; Driver program to test the above function
import javafx . util . Pair ; import java . util . ArrayList ; import java . util . * ; class GfG { public static int minSwaps ( int [ ] arr ) { int n = arr . length ; ArrayList < Pair < Integer , Integer > > arrpos = new ArrayList < Pair < Integer , Integer > > ( ) ; for ( int i = 0 ; i < n ; i ++ ) arrpos . add ( new Pair < Integer , Integer > ( arr [ i ] , i ) ) ; arrpos . sort ( new Comparator < Pair < Integer , Integer > > ( ) { @ Override public int compare ( Pair < Integer , Integer > o1 , Pair < Integer , Integer > o2 ) { if ( o1 . getKey ( ) > o2 . getKey ( ) ) return - 1 ; else if ( o1 . getKey ( ) . equals ( o2 . getKey ( ) ) ) return 0 ; else return 1 ; } } ) ; Boolean [ ] vis = new Boolean [ n ] ; Arrays . fill ( vis , false ) ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( vis [ i ] || arrpos . get ( i ) . getValue ( ) == i ) continue ; int cycle_size = 0 ; int j = i ; while ( ! vis [ j ] ) { vis [ j ] = true ; j = arrpos . get ( j ) . getValue ( ) ; cycle_size ++ ; } if ( cycle_size > 0 ) { ans += ( cycle_size - 1 ) ; } } return ans ; } } class MinSwaps { public static void main ( String [ ] args ) { int [ ] a = { 1 , 5 , 4 , 3 , 2 } ; GfG g = new GfG ( ) ; System . out . println ( g . minSwaps ( a ) ) ; } }