Searching and Sorting: Minimum number of swaps required to sort an array

Problem Statement:

You are given an array of distinct elements. You need to find the minimum number of swaps required to sort the array.

Example

Input : {4, 3, 2, 1}
Output : 2
We need to swap index 0 with 3 and 1 with 2 to make the array sorted.

Solution

The solution is very simple.

We iterate over the array, while iterating we check if the current element is in the correct place, if not, then we replace that element with the index of the element which should have come in this place.

Example

arr = [1, 4, 3, 2]

Here 1 is in correct place, 3 is in correct place.

4 and 2 are not in correct place.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 
#include <unordered_map> 

using namespace std;
  
void swap(vector<int> &arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
 
int index_of(vector<int> &arr, int ele)
{
    for(int i = 0; i < arr.size(); i++)
    {
        if (arr[i] == ele)
        {
            return i;
        }
    }
    return -1;
}

int get_min_swaps(vector<int> arr)
{
    int len = arr.size();
    int ans = 0;

    // temp array to store the sorted values
    vector<int> temp(arr.begin(),arr.end());
    sort(temp.begin(),temp.end());
     
    for(int i = 0; i < len; i++)
    {
         
        //check if the current element is at the right place or not
        if (arr[i] != temp[i])
        {
            ans++;
            
            // if not, then swap it with the right index element.
            // for that we need the index of the right most element.
            // hence we call one more function index_of to get the index of 
            // right most element
            swap(arr, i, index_of(arr, temp[i]));
        }
    }
    return ans;
}

int main()
{
 
    vector<int> arr = {1, 4, 3, 2};

    cout << "The min swaps required are = "<< get_min_swaps(arr)<<endl;
}

Output:

The min swaps required are = 1
Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *