Số lượng hoán đổi tối thiểu cần thiết để sắp xếp một mảng trong C ++

Tuyên bố vấn đề

Cho một mảng gồm N phần tử riêng biệt, hãy tìm số lượng hoán đổi tối thiểu cần thiết để sắp xếp mảng

Ví dụ

Nếu mảng là {4, 2, 1, 3} thì bắt buộc phải có 2 hoán đổi

• Hoán đổi arr [0] với arr [2]
• Hoán đổi arr [2] với arr [3}

Thuật toán

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.

Ví dụ

#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;
}

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau

Đầu ra

Minimum swaps = 2