समस्या कथन
N विशिष्ट तत्वों की एक सरणी को देखते हुए, सरणी को क्रमबद्ध करने के लिए आवश्यक न्यूनतम संख्या में स्वैप खोजें
उदाहरण
यदि सरणी {4, 2, 1, 3} है तो 2 स्वैप की आवश्यकता है
- गिरफ्तारी[0] को गिरफ्तारी के साथ बदलें[2]
- गिरफ्तारी की अदला-बदली करें[2] गिरफ्तारी के साथ[3}
एल्गोरिदम
1. Create a vector of pair in C++ with first element as array alues and second element as array indices. 2. Sort the vector of pair according to the first element of the pairs. 3. Traverse the vector and check if the index mapped with the value is correct or not, if not then keep swapping until the element is placed correctly and keep counting the number of swaps.
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n) {
vector<pair<int, int>> vec(n);
for (int i = 0; i < n; ++i) {
vec[i].first = arr[i];
vec[i].second = i;
}
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);
swap(vec[i].second,vec[vec[i].second].second);
if (i != vec[i].second) {
--i;
}
++cnt;
}
return cnt;
}
int main() {
int arr[] = {4, 2, 1, 3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum swaps = " << getMinSwaps(arr, n) <<
endl;
return 0;
} जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्न आउटपुट उत्पन्न करता है
आउटपुट
Minimum swaps = 2