Approach: As Pair class available in java from java 8 so we can use hashmap in older java version.
Below is the implementation of the idea.
import java.util.*;
import java.io.*;
class GfG
{
// Function returns the
// minimum number of swaps
// required to sort the array
public static int minSwaps( int [] nums)
{
int len = nums.length;
HashMap<Integer, Integer> map = new HashMap<>();
for ( int i= 0 ;i<len;i++)
map.put(nums[i], i);
Arrays.sort(nums);
// To keep track of visited elements. Initialize
// all elements as not visited or false.
boolean [] visited = new boolean [len];
Arrays.fill(visited, false );
// Initialize result
int ans = 0 ;
for ( int i= 0 ;i<len;i++) {
// already swapped and corrected or
// already present at correct pos
if (visited[i] || map.get(nums[i]) == i)
continue ;
int j = i, cycle_size = 0 ;
while (!visited[j]) {
visited[j] = true ;
// move to next node
j = map.get(nums[j]);
cycle_size++;
}
// Update answer by adding current cycle.
if (cycle_size > 0 ) {
ans += (cycle_size - 1 );
}
}
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));
}
}
Time Complexity: O(n Log n)
Auxiliary Space: O(n)
Straight forward solution
While iterating over the array, check the current element, and if not in the correct place, replace that element with the index of the element which should have come in this place.
Below is the implementation of the above approach:
// Java program to find
// minimum number of swaps
// required to sort an array
import java.util.*;
import java.io.*;
class GfG
{
// Return the minimum number
// of swaps required to sort the array
public int minSwaps( int [] arr, int N)
{
int ans = 0 ;
int [] temp = Arrays.copyOfRange(arr, 0 , N);
Arrays.sort(temp);
for ( int i = 0 ; i < N; i++)
{
// This is checking whether
// the current element is
// at the right place or not
if (arr[i] != temp[i])
{
ans++;
// Swap the current element
// with the right index
// so that arr[0] to arr[i] is sorted
swap(arr, i, indexOf(arr, temp[i]));
}
}
return ans;
}
public void swap( int [] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public int indexOf( int [] arr, int ele)
{
for ( int i = 0 ; i < arr.length; i++)
{
if (arr[i] == ele) {
return i;
}
}
return - 1 ;
}
}
// Driver class
class Main
{
// Driver program to test
// the above function
public static void main(String[] args)
throws Exception
{
int [] a
= { 101 , 758 , 315 , 730 , 472 ,
619 , 460 , 479 };
int n = a.length;
// Output will be 5
System.out.println( new GfG().minSwaps(a, n));
}
}
Output:
5
Time Complexity: O(n*n)
Auxiliary Space: O(n)