C++で配列をソートするために必要なスワップの最小数

問題の説明

N個の異なる要素の配列が与えられた場合、配列をソートするために必要なスワップの最小数を見つけます

例

配列が{4、2、1、3}の場合、2つのスワップが必要です

• arr[0]をarr[2]と交換します
• arr[2]をarr[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