Minimum Number of Swaps to Sort an Array

Introduction

Imagine you are given a bunch of food items to eat. It includes your favourite as well as your non-favourite food items.

Now you have to decide according to your preference which item you would like to eat first. And then, you will make necessary shuffling among the food items and sort them according to your eating preference.

Like many food items, an array is a programming tool that stores similar data together under a single name.

Consider elements in an unsorted array:

4

10

2

56

19

Like we sorted the food items according to our eating preference, we also sorted the elements in an array. And in both cases, we exchange the places of elements to assign them their correct position. 

We swapped the elements of an array to sort them in ascending order.

2

4

10

19

56

Now, after sorting, since we know the address of the first element, we can access other elements one after the other.

Thus, we can define swapping in array as:

The number of exchanges that occur while arranging or sorting the elements in the desired order.

So let us discuss all these methods one by one to know about various swaps used while sorting.

Minimum Swaps to Sort an Array

Consider an unsorted array consisting of integers, where n is the size of the array. We need to find the minimum number of swaps to sort an array in ascending order.

Let the array be:

1

4

11

2

5

What is the basic/brute approach one could go on with to minimise the number of swaps and sort the array side-by-side? 

Well, let’s have 11 at the second index, as shown in the above example. Now we have 2 options. Swap 11 with 2 or with 5. Which one would you choose?

The obvious answer would be swapping with 5 because swapping with 2 would mean another swap with 5, which would result in 2 swaps for the same element, but to find the minimum number of swaps to sort the array, it only makes sense to swap with the number such that both the elements are swapped in the correct sorted order.

NOTE: The above explanation is just to understand what choices are available and which one to choose and why? 

So at each index, we should find the one that places a particular element in just a single swap at its correct place. 

Do you recall, Which sorting algorithm we are talking about? 

If your answer is Selection Sort. You got it correct.

Selection sort makes at most N-1 swaps. Nevertheless, we found an algorithm that fulfills the criteria and takes O(n²) time. 

Remember, we always want to get better and better. So let’s try to rethink and improve our solution.

If you are stuck on how one improves their solution, then the tip of advice is to check redundancies, repetitive work, which could be prevented. Try to think whether any other technique does the same job in less time. 

Why does the above idea work? (Intuition)

Consider an array to be written as a₁, a₂, …a_j-1, a_j , a_j+1, .. a_N .

and assume that {a₁ , a_j-2} and  {a_j+2 , a_N}  are already at their correct positions.

The algorithm gave us the correct answers for sorting both parts in a minimum number of steps. Say it took X steps. 

The only segment to be sorted in minimum number moves is the segment containing a_j-1, a_j , a_j+1.

_{Now consider the following cases:}

1. a_j-1 <= a_j <= a_j+1   no swaps are needed.
2. a_j-1 > a_j >= a_j+1   , only 1 swap is needed.
3. a_j-1 >= a_j > a_j+1  ,  only 1 swap is needed.    
4. a_j-1 < a_j > a_j+1 , we can 2 sub-cases here,
   1. a_j-1 <= a_j+1 , only 1 swap is needed.
   2. a_j-1 > a_j+1 ,  here 2 swaps are needed. 

We have exhausted all the possible cases. See, every time we search for the element to be placed at a particular position in sorted order, we search for the minimum on the right-hand side and swap it with the current element, which gives us the optimal answer.

Choosing another swapping mechanism would be contradictory if we assumed that the above algorithm gave us the incorrect result.

Approach 

Let’s see a general approach to solving the problem without thinking about any data structures.

• We want to place an element at its correct position. So, if an element already presents at its sorted order position, then we won’t be swapping that element.

• But if the element at a position doesn’t match with the element present at the same position in the sorted array, then place the correct element at that position and look where we could place the incorrectly placed element. 

• Repeat the process until we reach a position where both the sorted array and the current array contain the same elements.

So, let’s look at several efficient techniques for calculating the minimum number of swaps to sort an array.

1. Hashing Approach

We will store elements in the array as a pair of values and their index positions as keys.

1. Sort the given array based on their values. Please Note we could include duplicate values as well. So if the current element’s value in the sorted array is equal to the element or the index is equal to the hashed index position in the original array. No swap is needed, and we can move to the next iteration.

2. But if the above condition doesn’t hold, we will swap the element, say at i^th index element of the array with the hashed index element in the array.

3. Keep on doing this until we don’t satisfy the above criterion (1).

4. Now increment the answer.

Code in C++:

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

int findMinSwap(vector<int> &arr, int n)
{
    // temporary vector to store values, along with its index in the original vector
    vector<pair<int, int>> temp(n);
    for (int i = 0; i < n; i++)
    {
        // values in the vector
        temp[i].first = arr[i];
        // index of the particular value.
        temp[i].second = i;
    }

    //sort the temp vector according to the values
    sort(temp.begin(), temp.end());
    // variable to store the answer
    int minimum_swaps = 0;
    int i = 0;
    while (i < n)
    {
        // If there is no need to swap then continue
        if (temp[i].second == i or temp[i].first == arr[i])
        {
            ++i;
            continue;
        }
        else
        {
            // swap the values accordingly
            swap(temp[i].first, temp[temp[i].second].first);
            // swap the indices also within the temp array also
            swap(temp[i].second, temp[temp[i].second].second);
            // stay on the same position until, we fulfill the criterion
            if (temp[i].second != i)
                i--;
        }
        //increment the answer
        minimum_swaps++;
        // move to the next index
        ++i;
    }
    return minimum_swaps;
}

int main()
{
    vector<int> arr = {1, 4, 3, 2};
    int n = arr.size();
    cout << "Minimum number of swaps required: " << findMinSwap(arr, n) << '\n';
}

Output

Minimum number of swaps required: 1

• Time Complexity: O(n log n)
• Space complexity: O(n)

2. Graph Approach

This method is nothing fancy w.r.t the above approach. It’s another dimension to visualize the problem. 

(Tip of advice: Visualizing the same problem in different ways will help you think of different ideas to solve a problem and reach the most optimised solution.)

Look at the following example:

Let’s see how we can sort the array in a minimum number of swaps.

So in the above example, we sort the array in 2 swaps.

Now see how the swaps are being made in the above figure. 

The element at the 3rd index should be placed at the 4th index, element at the 2nd index should be placed at the 5th index. It can be visualized as a node at index i being connected to the node at index j, where the number of nodes in the graph is n.

Now, how to compute the answer?? 

Notice that a swap can be thought of as a cycle going from index i to index j and then from index j to index i. 

no. of all cycles

The number of swaps will be =  no. of all cycles ∑ (Size of cycle – 1).

Code in C++:

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

int findMinSwap(vector<int> &arr, int n)
{
    // vector to store values
    vector<pair<int, int>> graph(n);
    // along with its index in the original vector
    for (int i = 0; i < n; i++)
    {
        // values in the vector
        graph[i].first = arr[i];
        // index of the particular value.
        graph[i].second = i;
    }

    //sort the vector according to the values
    sort(graph.begin(), graph.end());

    // variable to store the answer
    int minimum_swaps = 0;
    int i = 0;
    while (i < n)
    {
        // If there is no need to swap then continue
        if (graph[i].second == i || graph[i].first == arr[i])
        {
            ++i;
            continue;
        }
        else
        {
            // cycle size
            int cycle_size = 0;
            // stay on the same position until, we fulfill the criterion
            while ((graph[i].second != i && graph[i].first != arr[i]))
            {

                // swap the values accordingly
                swap(graph[i].first, graph[graph[i].second].first);
                // swap the indices also within the graph vector also
                swap(graph[i].second, graph[graph[i].second].second);
                // increment cycle size
                cycle_size++;
            }
            //add the cycle size to swaps.
            if (cycle_size > 0)
                minimum_swaps += (cycle_size);
            // move to the next index
            ++i;
        }
    }
    return minimum_swaps;
}

int main()
{
    vector<int> arr = {4, 3, 2, 1};
    int n = arr.size();
    cout << "Minimum number of swaps required: " << findMinSwap(arr, n) << '\n';
}

Output

Minimum number of swaps required: 2

• Time Complexity: O(n log n) 
• Space Complexity: O(n)

Frequently Asked Questions

Key Takeaways

This article taught us the minimum number of swaps to sort an array in the C++ programming language. We discussed their implementation using the hashing and graph method.

Now, we recommend you practice problem sets based on these concepts to master your skills. You can get a wide range of questions similar to the minimum number of swaps to sort an array on Code studio. 

By: Aniket Verma