সমস্যা বিবরণ
N ভিন্ন এলিমেন্টের একটি অ্যারে দেওয়া আছে, অ্যারে সর্ট করার জন্য ন্যূনতম কতগুলো সোয়াপ দরকার তা বের করুন।
উদাহরণ
অ্যারে {4, 2, 1, 3} হলে ২টি সোয়াপ দরকার:
- arr[0] এবং arr[2] সোয়াপ
- arr[2] এবং arr[3] সোয়াপ
অ্যালগরিদম
1. C++-তে pair-এর ভেক্টর বানান যেখানে first = অ্যারে ভ্যালু, second = অ্যারে ইনডেক্স। 2. পেয়ারের ভেক্টরকে first এলিমেন্ট অনুযায়ী সর্ট করুন। 3. ভেক্টর ট্র্যাভার্স করুন এবং চেক করুন ইনডেক্স ম্যাপিং ঠিক আছে কিনা, না হলে এলিমেন্ট সঠিক জায়গায় না আসা পর্যন্ত সোয়াপ করুন এবং সোয়াপ কাউন্ট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n) {
vector> 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
