Minimum number of swaps required to sort a given array

Problem Statement: Given an array of n distinct elements, we have to find the minimum number of swaps required to sort the given array.

Example –

Input array - {2, 4, 5, 3, 1, 6}
Output - 4
Explanation - Swap index 0 with index 4 => {1, 4, 5, 3, 2, 6}
              Swap index 1 with index 4 => {1, 2, 5, 3, 4, 6}
              Swap index 2 with index 3 => {1, 2, 3, 5, 4, 6}
              Swap index 3 with index 4 => {1, 2, 3, 4, 5, 6}

Input array - {9, 8, 5, 3}
Output - 2
Explanation - Swap index 0 with index 3 => {3, 8, 5, 9}
              Swap index 1 with index 2 => {3, 5, 8, 9}

Approach

This problem can easily be solved using graphs. Consider all the n elements of an array as the nodes of a graph. Now there exists a directed edge between the node i and node j, if the correct position of the node at ith index is the jth index in the sorted array.

Do this for all the edges (i.e. draw an edge from their current position to actual position in the sorted array). Once edges are drawn for all the nodes, multiple(min 1) cycle will be formed. Hence the minimum number of nodes required to sort an array will be (the sum of all the cycle size decreased by 1) :

 min swaps = Σ(cycles_size – 1)

Consider the example array – {2, 4, 5, 3, 1, 6}. The graph for this array will look like as shown below –
There are two cycles in this graph one of length 5 {1->2->4->3->5->1}  and the other of length 1 {6-6}. Hence the minimum number of swaps required to sort this array is 4 (i.e. (5-1) + (1-1)).

Algorithm

1. Consider all elements of an array as vertices of a graph.
2. Create a directed edge b/w every node and its correct position.
3. Find the total number of cycles and size of each cycle.
4. The minimum number of swaps required is the sum of all cycle sizes decreased by 1.

Implementation of the above Algorithm

// C++ program to find minimum number of swaps
// required to sort an array
#include<bits/stdc++.h>
using namespace std;

// Function returns the minimum number of swaps 
// required to sort the array 
int minSwaps(int arr[], int n) 
{ 
    int res = 0, cycle_len = 0;
    
    //keeps track of visited elements
    int visited[n] = {0};

    // Create an array of pairs where first 
    // element is array element and second element 
    // is position of first element     
    vector<pair<int, int> >graph;


    for(int i=0; i<n; i++)
        graph.push_back({arr[i], i});
    
    // Sort the array by array element values to 
    // get right position of every element as second 
    // element of pair.
    sort(graph.begin(), graph.end());

    for(int i=0; i<n; i++)
    {
        //if current element is in its correct position
        //or is already visited 
        if(visited[i] == 1 || graph[i].second == i)
            continue;

        //find the total number of nodes in the cycle
        //(cycle length) starting from current node 
        else
        {
            int j = i;

            //Initialize the current length to 0
            cycle_len = 0;

            //find out the number of nodes in the 
            //cycle and mark them visited
            while(1)
            {
                //if current node is already visited
                //exit the loop
                if(visited[j] == 1)
                    break;

                visited[j] = 1;
                j = graph[j].second;
                cycle_len++;
            }

            //update the final result by adding 
            //current cycle length - 1
            res = res + cycle_len - 1;
        }
    }

    //return minimum number of swaps required 
    //to sort an array
    return res;
} 

//Main code 
int main()
{

    int arr[] = {2, 4, 5, 3, 1, 6};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout<<minSwaps(arr,n)<<endl;

    return 0;
}

Output
4

Time Complexity

The run time complexity of the above algorithm is O(NlogN), where N is the number of elements in the given array. The auxiliary space complexity is O(N).

If you found anything incorrect or want to suggest improvements, please comment.