We can still improve the complexity by using a hashmap. The main operation here is the indexOf method inside the loop, which costs us n*n. We can improve this section to O(n), by using a hashmap to store the indexes. Still, we use the sort method, so the complexity cannot improve beyond O(n Log n)
Method using HashMap:
Same as before, make a new array (called temp), which is the sorted form of the input array. We know that we need to transform the input array to the new array (temp) in the minimum number of swaps. Make a map that stores the elements and their corresponding index, of the input array.
So at each i starting from 0 to N in the given array, where N is the size of the array:
-
If i is not in its correct position according to the sorted array, then
-
We will fill this position with the correct element from the hashmap we built earlier. We know the correct element which should come here is temp[i], so we look up the index of this element from the hashmap.
-
After swapping the required elements, we update the content of the hashmap accordingly, as temp[i] to the ith position, and arr[i] to where temp[i] was earlier.
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);
// Hashmap which stores the
// indexes of the input array
HashMap<Integer, Integer> h
= new HashMap<Integer, Integer>();
Arrays.sort(temp);
for ( int i = 0 ; i < N; i++)
{
h.put(arr[i], i);
}
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++;
int init = arr[i];
// If not, swap this element
// with the index of the
// element which should come here
swap(arr, i, h.get(temp[i]));
// Update the indexes in
// the hashmap accordingly
h.put(init, h.get(temp[i]));
h.put(temp[i], i);
}
}
return ans;
}
public void swap( int [] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 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 Log n)
Auxiliary Space: O(n)