Given an array arr[] of distinct integers from 1 to N. The task is to find the minimum number of swaps required to sort the array.
Example:
Input: arr[] = { 7, 1, 3, 2, 4, 5, 6 }
Output: 5
Explanation:
i arr swap (indices)
0 [7, 1, 3, 2, 4, 5, 6] swap (0, 3)
1 [2, 1, 3, 7, 4, 5, 6] swap (0, 1)
2 [1, 2, 3, 7, 4, 5, 6] swap (3, 4)
3 [1, 2, 3, 4, 7, 5, 6] swap (4, 5)
4 [1, 2, 3, 4, 5, 7, 6] swap (5, 6)
5 [1, 2, 3, 4, 5, 6, 7]
Therefore, total number of swaps = 5
Input: arr[] = { 2, 3, 4, 1, 5 }
Output: 3
Approach:
- For each index in arr[].
- Check if the current element is in it’s right position or not. Since the array contains distinct elements from 1 to N, we can simply compare the element with it’s index in array to check if it is at its right position.
- If current element is not at it’s right position then swap the element with the element which has occupied its place.
- Else check for next index.
Below is the implementation of the above approach:
// Java program to find the minimum
// number of swaps required to sort
// the given array
import java.io.*;
import java.util.*;
class GfG {
// Function to find minimum swaps
static int minimumSwaps( int [] arr)
{
// Initialise count variable
int count = 0 ;
int i = 0 ;
while (i < arr.length) {
// If current element is
// not at the right position
if (arr[i] != i + 1 ) {
while (arr[i] != i + 1 ) {
int temp = 0 ;
// Swap current element
// with correct position
// of that element
temp = arr[arr[i] - 1 ];
arr[arr[i] - 1 ] = arr[i];
arr[i] = temp;
count++;
}
}
// Increment for next index
// when current element is at
// correct position
i++;
}
return count;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2 , 3 , 4 , 1 , 5 };
// Function to find minimum swaps
System.out.println(minimumSwaps(arr));
}
}
Output:
3
Time Complexity: O(N) where N is the size of array.
Auxiliary Space: O(1)