https://www.tutorialspoint.com/minimum-number-of-swaps-required-to-sort-an-array-in-cplusplus
Please help me to understand this concept and code!
Minimum swaps to sort array
@archa_1712
we have created a vector of pairs and we have pushed in values and index.we have sorted the vector acc to values…now we compare the indexes of sorted values and pair.second index.if they both are same that means the value is where it is supposed to be .and whenever its not we swap and increase the count of swap.this way we get the min no of swaps required
@archa_1712
vector<pair<int, int>> vec(n); //a vector of pairs
for (int i = 0; i < n; ++i) {
vec[i].first = arr[i]; //pushed in values
vec[i].second = i; //and index
}
sort(vec.begin(), vec.end());
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (vec[i].second == i) {
continue;
}
swap(vec[i].first,vec[vec[i].second].first); //sorted the vector acc to values
swap(vec[i].second,vec[vec[i].second].second);
if (i != vec[i].second) { //compare the indexes of sorted values and pair.second index
–i; //we swap and increase the count of swap
}
++cnt;
}
return cnt;
okay thank you!..!
