Tutorialspoint.dev

Minimum number of swaps required to sort an array

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

Examples:

Input : {4, 3, 2, 1}
Output : 2
Explanation : Swap index 0 with 3 and 1 with 2 to 
              form the sorted array {1, 2, 3, 4}.

Input : {1, 5, 4, 3, 2}
Output : 2

This can be easily done by visualizing the problem as a graph. We will have n nodes and an edge directed from node i to node j if the element at i’th index must be present at j’th index in the sorted array.



a
Graph for {4, 3, 2, 1}

The graph will now contain many non-intersecting cycles. Now a cycle with 2 nodes will only require 1 swap to reach the correct ordering, similarly a cycle with 3 nodes will only require 2 swap to do so.

b
Graph for {4, 5, 2, 1, 5}

Hence,

  • ans = Σi = 1k(cycle_size – 1)
  • where k is the number of cycles

    Below is the implementation of the idea.

    C++



    // 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)
    {
        // Create an array of pairs where first
        // element is array element and second element
        // is position of first element
        pair<int, int> arrPos[n];
        for (int i = 0; i < n; i++)
        {
            arrPos[i].first = arr[i];
            arrPos[i].second = i;
        }
      
        // Sort the array by array element values to
        // get right position of every element as second
        // element of pair.
        sort(arrPos, arrPos + n);
      
        // To keep track of visited elements. Initialize
        // all elements as not visited or false.
        vector<bool> vis(n, false);
      
        // Initialize result
        int ans = 0;
      
        // Traverse array elements
        for (int i = 0; i < n; i++)
        {
            // already swapped and corrected or
            // already present at correct pos
            if (vis[i] || arrPos[i].second == i)
                continue;
      
            // find out the number of  node in
            // this cycle and add in ans
            int cycle_size = 0;
            int j = i;
            while (!vis[j])
            {
                vis[j] = 1;
      
                // move to next node
                j = arrPos[j].second;
                cycle_size++;
            }
      
            // Update answer by adding current cycle. 
            if (cycle_size > 0)
            {
                ans += (cycle_size - 1);
            }
        }
      
        // Return result
        return ans;
    }
      
    // Driver program to test the above function
    int main()
    {
        int arr[] = {1, 5, 4, 3, 2};
        int n = (sizeof(arr) / sizeof(int));
        cout << minSwaps(arr, n);
        return 0;
    }

    Java

    // Java program to find  minimum number of swaps
    // required to sort an array
    import javafx.util.Pair;
    import java.util.ArrayList;
    import java.util.*;
      
    class GfG
    {
        // Function returns the minimum number of swaps
        // required to sort the array
        public static int minSwaps(int[] arr)
        {
            int n = arr.length;
      
            // Create two arrays and use as pairs where first
            // array is element and second array
            // is position of first element
            ArrayList <Pair <Integer, Integer> > arrpos =
                      new ArrayList <Pair <Integer, Integer> > ();
            for (int i = 0; i < n; i++)
                 arrpos.add(new Pair <Integer, Integer> (arr[i], i));
      
            // Sort the array by array element values to
            // get right position of every element as the
            // elements of second array.
            arrpos.sort(new Comparator<Pair<Integer, Integer>>()
            {
                @Override
                public int compare(Pair<Integer, Integer> o1,
                                   Pair<Integer, Integer> o2)
                {
                    if (o1.getKey() > o2.getKey())
                        return -1;
      
                    // We can change this to make it then look at the
                    // words alphabetical order
                    else if (o1.getKey().equals(o2.getKey()))
                        return 0;
      
                    else
                        return 1;
                }
            });
      
            // To keep track of visited elements. Initialize
            // all elements as not visited or false.
            Boolean[] vis = new Boolean[n];
            Arrays.fill(vis, false);
      
            // Initialize result
            int ans = 0;
      
            // Traverse array elements
            for (int i = 0; i < n; i++)
            {
                // already swapped and corrected or
                // already present at correct pos
                if (vis[i] || arrpos.get(i).getValue() == i)
                    continue;
      
                // find out the number of  node in
                // this cycle and add in ans
                int cycle_size = 0;
                int j = i;
                while (!vis[j])
                {
                    vis[j] = true;
      
                    // move to next node
                    j = arrpos.get(j).getValue();
                    cycle_size++;
                }
      
                // Update answer by adding current cycle.
                if(cycle_size > 0)
                {
                    ans += (cycle_size - 1);
                }
            }
      
            // Return result
            return ans;
        }
    }
      
    // Driver class
    class MinSwaps
    {
        // Driver program to test the above function
        public static void main(String[] args)
        {
            int []a = {1, 5, 4, 3, 2};
            GfG g = new GfG();
            System.out.println(g.minSwaps(a));
        }
    }
    // This code is contributed by Saksham Seth

    [/sourcecode]

    Python3

    # Python3 program to find  minimum number 
    # of swaps required to sort an array
      
    # Function returns the minimum 
    # number of swaps required to sort the array
    def minSwaps(arr):
        n = len(arr)
          
        # Create two arrays and use 
        # as pairs where first array 
        # is element and second array
        # is position of first element
        arrpos = [*enumerate(arr)]
          
        # Sort the array by array element 
        # values to get right position of 
        # every element as the elements 
        # of second array.
        arrpos.sort(key = lambda it:it[1])
          
        # To keep track of visited elements. 
        # Initialize all elements as not 
        # visited or false.
        vis = {k:False for k in range(n)}
          
        # Initialize result
        ans = 0
        for i in range(n):
              
            # alreadt swapped or 
            # alreadt present at 
            # correct position
            if vis[i] or arrpos[i][0] == i:
                continue
                  
            # find number of nodes 
            # in this cycle and
            # add it to ans
            cycle_size = 0
            j = i
            while not vis[j]:
                  
                # mark node as visited
                vis[j] = True
                  
                # move to next node
                j = arrpos[j][0]
                cycle_size += 1
                  
            # update answer by adding
            # current cycle
            if cycle_size > 0:
                ans += (cycle_size - 1)
        # return answer
        return ans
      
    # Driver Code     
    arr = [1, 5, 4, 3, 2]
    print(minSwaps(arr))
      
    # This code is contributed
    # by Dharan Aditya


    Output:

    2
    

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

    Related Article :
    Number of swaps to sort when only adjacent swapping allowed

    Reference:
    http://stackoverflow.com/questions/15152322/compute-the-minimal-number-of-swaps-to-order-a-sequence/15152602#15152602



    This article is attributed to GeeksforGeeks.org

    leave a comment

    code

    0 Comments

    load comments

    Subscribe to Our Newsletter