Minimum Swaps required to Sort

Given an array . Find the minimum number of swaps required to sort the array in non-decreasing order.

Example 1:
Input:
N = 5
arr = {1 5 4 3 2}
Output: 2
Explaination: swap 2 with 5 and 3 with 4.
 
Example 2:
Input:
N = 4
arr[] = {8 9 16 15}
Output: 1

Explaination: swap 16 and 15.

method 1:

int minSwaps(int a[], int n)
{   int temp[n]; int c=0; int k=0;

  for(int i=0;i<n;i++)
  temp[i]=a[i];

  sort(temp,temp+n);
  
  for(int i=0;i<n;i++)
 {
     if(a[i]!=temp[i])
     {
         c++;
        for (int j = 0; j < n; j++) 
        {
            if (a[j] == temp[i]) {

                 k=j;

                break;
            }
        }
        swap(a[i],a[k]);
     }
 }
 return c ;
}

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

method 2:

int minSwaps(int a[], int n)
{    int c=0; 
       vector<pair<int,int>>v(n);
       
  for(int i=0;i<n;i++)
  v[i]=make_pair(a[i],i);

  sort(v.begin(),v.end());
  
  for(int i=0;i<n;i++)
 {
    if(v[i].second!=i)
    {  c++;
        swap(v[v[i].second],v[i]);
        i--;
    }
    
 }
 return c ;
}

Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)