Minimum no of swaps required to sort the array
Minimum no of swaps required to sort the array
Can I solve it without graph
Not getting logic of the problem
hi @kumarakash121005
yes u can do it without graphs alsoâ€¦ scroll down the link, u will get other approach alsoâ€¦
Is this problem same as selection sort
noâ€¦ not selection sort as suchâ€¦
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.
@kumarakash121005 this problem can be solved using 1) Graphs 2) hashing.
Since you are more concerned about the nongraph 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.

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.

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.

Keep on doing this until we donâ€™t satisfy the above criterion (1).

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
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.