Given an array of n distinct elements, find the minimum number of swaps required to sort the array.
Examples:
Input: {4, 3, 2, 1}
Output: 2
Explanation: Swap index 0 with 3 and 1 with 2 to
form the sorted array {1, 2, 3, 4}.
Input: {1, 5, 4, 3, 2}
Output: 2
Below is the implementation of the idea.
// Java program to find
// minimum number of swaps
// required to sort an array
import javafx.util.Pair;
import java.util.ArrayList;
import java.util.*;
class GfG
{
// Function returns the
// minimum number of swaps
// required to sort the array
public static int minSwaps( int [] arr)
{
int n = arr.length;
// Create two arrays and
// use as pairs where first
// array is element and second array
// is position of first element
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));
// Sort the array by array element values to
// get right position of every element as the
// elements of second array.
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 ;
// We can change this to make
// it then look at the
// words alphabetical order
else if (o1.getKey().equals(o2.getKey()))
return 0 ;
else
return 1 ;
}
});
// To keep track of visited elements. Initialize
// all elements as not visited or false.
Boolean[] vis = new Boolean[n];
Arrays.fill(vis, false );
// Initialize result
int ans = 0 ;
// Traverse array elements
for ( int i = 0 ; i < n; i++)
{
// already swapped and corrected or
// already present at correct pos
if (vis[i] || arrpos.get(i).getValue() == i)
continue ;
// find out the number of node in
// this cycle and add in ans
int cycle_size = 0 ;
int j = i;
while (!vis[j])
{
vis[j] = true ;
// move to next node
j = arrpos.get(j).getValue();
cycle_size++;
}
// Update answer by adding current cycle.
if (cycle_size > 0 )
{
ans += (cycle_size - 1 );
}
}
// Return result
return ans;
}
}
// Driver class
class MinSwaps
{
// Driver program to test the above function
public static void main(String[] args)
{
int []a = { 1 , 5 , 4 , 3 , 2 };
GfG g = new GfG();
System.out.println(g.minSwaps(a));
}
}
Output:
2
Time Complexity: O(n Log n)
Auxiliary Space: O(n)