Minimum number of swaps required to sort an array using Hashmap

Software Development
1

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:

  1. If i is not in its correct position according to the sorted array, then
  2. 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.
  3. 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:
    // C++ program to find
    // minimum number of swaps
    // required to sort an array
    #include<bits/stdc++.h>
    using namespace std;

void swap(vector &arr,
int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Return the minimum number
// of swaps required to sort
// the array
int minSwaps(vectorarr,
int N)
{
int ans = 0;
vectortemp = arr;

// Hashmap which stores the
// indexes of the input array
map <int, int> h;

sort(temp.begin(), temp.end());
for (int i = 0; i < N; i++)
{
h[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[temp[i]]);

  // Update the indexes in
  // the hashmap accordingly
  h[init] = h[temp[i]];
  h[temp[i]] = i;
}

}
return ans;
}

// Driver class
int main()
{
// Driver program to
// test the above function
vector a = {101, 758, 315,
730, 472, 619,
460, 479};
int n = a.size();

// Output will be 5
cout << minSwaps(a, n);
}

Output:
5
Time Complexity: O(n Log n)
Auxiliary Space: O(n)