Minimum no of swaps required to sort the array

#1

Minimum no of swaps required to sort the array

#2

hi @kumarakash121005
refer this -->


u will get very good explanation with code…

#3

Can I solve it without graph

#4

Not getting logic of the problem

#5

hi @kumarakash121005
yes u can do it without graphs also… scroll down the link, u will get other approach also…

#6

Is this problem same as selection sort

#7

no… not selection sort as such…

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#9

@kumarakash121005 this problem can be solved using 1) Graphs 2) hashing.
Since you are more concerned about the non-graph approach I will try to explain to you the Hashmap 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 ith 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.

Reffer to below code for more understanding of the approach

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

int findMinSwap(vector &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(temp[i].first, temp[temp[i].second].first);
        swap(temp[i].second, temp[temp[i].second].second);
        if (temp[i].second != i)
            i--;
    }
    //increment the answer
    minimum_swaps++;
    // move to the next index
    ++i;
}
return minimum_swaps;

}

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

Hope this helps :slight_smile:

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.