[02 Feb 2020] Given an array of N distinct elements, find the minimum number of swaps required to sort the array.

Given an array of N distinct elements, find the minimum number of swaps required to sort the array.

#include<bits/stdc++.h>
using namespace std;

// Function to find minimum swaps to
// sort an array
int findMinSwap(int arr[] , int n)
{
    // Declare a vector of pair   
    vector<pair<int,int>> vec(n);
   
    for(int i=0;i<n;i++)
    {
        vec[i].first=arr[i];
        vec[i].second=i;
    }

    // Sort the vector w.r.t the first
    // element of pair
    sort(vec.begin(),vec.end());

    int ans=0,c=0,j;

    for(int i=0;i<n;i++)
    { 
        // If the element is already placed
        // correct, then continue
        if(vec[i].second==i)
            continue;
        else
        {
            // swap with its respective index
            swap(vec[i].first,vec[vec[i].second].first);
            swap(vec[i].second,vec[vec[i].second].second);
        }
       
        // swap until the correct
        // index matches
        if(i!=vec[i].second)
            --i;
       
        // each swap makes one element
        // move to its correct index,
        // so increment answer
        ans++;
    }

    return ans;
}

// Driver code
int main()
{
    int arr[] = {1, 5, 4, 3, 2};
   
    int n = sizeof(arr)/sizeof(arr[0]);
   
    cout<<findMinSwap(arr,n);
   
    return 0;
}
Output:
2

# Python3 program to find the minimum number
# of swaps required to sort an array
# of distinct element

# Function to find minimum swaps to
# sort an array
def findMinSwap(arr, n):
   
    # Declare a vector of pair
    vec = []

    for i in range(n):
        vec.append([arr[i], i])

    # Sort the vector w.r.t the first
    # element of pair
    vec = sorted(vec)

    ans, c, j = -1, 0, 0

    for i in range(n):
       
        # If the element is already placed
        # correct, then continue
        if(vec[i][1] == i):
            continue
        else:
            # swap with its respective index
            vec[i][0], vec[vec[i][1]][1] = \
                vec[vec[i][1]][1], vec[i][0]
            vec[i][1], vec[vec[i][1]][1] = \
                vec[vec[i][1]][1], vec[i][1]

        # swap until the correct
        # index matches
        if(i != vec[i][1]):
            i -= 1

        # each swap makes one element
        # move to its correct index,
        # so increment answer
        ans += 1

    return ans

# Driver code
arr = [1, 5, 4, 3, 2]
n = len(arr)
print(findMinSwap(arr,n))

# This code is contributed by mohit kumar 29
Output:
2