【C++】配列をソートするために必要な最小スワップ回数を求める方法

問題文

N個の互いに異なる要素からなる配列が与えられたとき、その配列を昇順にソートするために必要な最小のスワップ（要素の入れ替え）回数を求めます。

例

たとえば、配列が {4, 2, 1, 3} の場合、必要なスワップは 2回 です。

• arr[0]（4）と arr[2]（1）を交換 → 配列は {1, 2, 4, 3} になります
• arr[2]（4）と arr[3]（3）を交換 → 配列は {1, 2, 3, 4} となり、ソート完了です

アルゴリズム

1. C++で pair の vector を作成します。first には配列の値を、second には元の配列におけるインデックスを格納します。
2. pair の first（値）を基準にして vector をソートします。
3. vector を先頭から走査し、各値に紐づくインデックスが正しい位置かどうかを確認します。正しくない場合は、その要素が正しい位置に収まるまでスワップを繰り返し、同時にスワップ回数をカウントしていきます。

サンプルコード

#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

ポイント解説

この手法のポイントは、値と元のインデックスをペアにしてソートすることで、「ソート後の正しい位置」と「現在の位置」の対応関係を容易に把握できる点にあります。ある要素がまだ正しい位置になければ、その要素が指し示す相手と入れ替える操作を繰り返すことで、必ず正しい位置へ移動させることができます。

計算量はソート処理が支配的となるため O(n log n) です。また、このアルゴリズムは配列内の要素がすべて異なる（重複がない）ことを前提としている点にも注意してください。