समस्या कथन
N विशिष्ट तत्वों की एक सरणी दी गई है, सरणी को क्रमबद्ध करने के लिए आवश्यक न्यूनतम स्वैप की संख्या ज्ञात करें
उदाहरण
यदि सरणी {4, 2, 1, 3} है तो 2 स्वैप आवश्यक हैं
- arr[0] को arr[2] से स्वैप करें
- arr[2] को arr[3] से स्वैप करें
एल्गोरिदम
1. C++ में जोड़ी का एक वेक्टर बनाएं जिसमें पहला तत्व सरणी मान और दूसरा तत्व सरणी इंडेक्स हो। 2. जोड़ों के वेक्टर को जोड़ों के पहले तत्व के अनुसार क्रमबद्ध करें। 3. वेक्टर को पार करें और जांचें कि मान के साथ मैप किया गया इंडेक्स सही है या नहीं, यदि नहीं तो तब तक स्वैप करते रहें जब तक तत्व सही ढंग से न रखा जाए और स्वैप की संख्या गिनते रहें।
उदाहरण
#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 << "न्यूनतम स्वैप = " << getMinSwaps(arr, n) << endl; return 0; }जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है
आउटपुट
न्यूनतम स्वैप = 2
