C/C++でマージソートを使って配列の転倒数（反転数）を数える方法

転倒（反転）とは？

配列の「転倒（inversion）」とは、その配列をソート済みの状態に変換するために必要な入れ替えの回数を表す指標です。配列がすでに昇順にソートされている場合、転倒数は0になります。逆に、配列が完全に逆順（降順）になっている場合、転倒数は最大となります。

この問題を、隣接するすべてのペアを総当たりで調べる素朴な方法で解くと、計算量はO(n²)になります。そこで本記事では、マージソートの仕組みを利用した分割統治法（Divide and Conquer）を採用し、計算量をO(n log n)まで抑える効率的なアプローチを紹介します。

入出力例

入力

数値の列：（1, 5, 6, 4, 20）

出力

数値を昇順に並べ替えるために必要な転倒の回数を出力します。

この場合、転倒数は2です。
1回目の転倒：（1, 5, 4, 6, 20）
2回目の転倒：（1, 4, 5, 6, 20）

アルゴリズム

merge(array, tempArray, left, mid, right)

入力：マージ対象となる2つの配列、および left・mid・right の各インデックス
出力：ソート済みの順序でマージされた配列

開始
   i := left、j := mid、k := right
   count := 0
   i <= mid - 1 かつ j <= right の間、繰り返し
      もし array[i] <= array[j] ならば
         tempArray[k] := array[i]
         i と k を1ずつ増やす
      そうでなければ
         tempArray[k] := array[j]
         j と k を1ずつ増やす
         count := count + (mid - i)
   繰り返し終了
   配列の左半分に要素が残っている間、繰り返し
      tempArray[k] := array[i]
      i と k を1ずつ増やす
   繰り返し終了
   配列の右半分に要素が残っている間、繰り返し
      tempArray[k] := array[j]
      j と k を1ずつ増やす
   繰り返し終了
   count を返す
終了

mergeSort(array, tempArray, left, right)

入力：対象の配列と作業用の一時配列、および配列の左端・右端のインデックス
出力：ソート完了時の転倒数

開始
   count := 0
   もし right > left ならば
      mid := (right + left) / 2
      count := mergeSort(array, tempArray, left, mid)
      count := count + mergeSort(array, tempArray, mid + 1, right)
      count := count + merge(array, tempArray, left, mid + 1, right)
   count を返す
終了

C++での実装例

#include <iostream>
using namespace std;
int merge(int arr[], int temp[], int left, int mid, int right) {
    int i, j, k;
    int count = 0;
    i = left; // 左側配列の位置を指す
    j = mid; // 右側配列の位置を指す
    k = left; // マージ後の配列の位置を指す
    while ((i <= mid - 1) && (j <= right)) {
        if (arr[i] <= arr[j]) { // 左側の要素が右側以下の場合
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            count += (mid - i); // 発生した転倒の数を加算
        }
    }
    while (i <= mid - 1) // 左側リストに残りがあれば追加
        temp[k++] = arr[i++];
    while (j <= right) // 右側リストに残りがあれば追加
        temp[k++] = arr[j++];
    for (i = left; i <= right; i++)
        arr[i] = temp[i]; // 一時配列の内容を元の配列へコピー
    return count;
}
int mergeSort(int arr[], int temp[], int left, int right) {
    int mid, count = 0;
    if (right > left) {
        mid = (right + left) / 2; // 配列の中間インデックスを求める
        count = mergeSort(arr, temp, left, mid); // 左側の部分配列をソート
        count += mergeSort(arr, temp, mid + 1, right); // 右側の部分配列をソート
        count += merge(arr, temp, left, mid + 1, right); // 2つの部分配列をマージ
    }
    return count;
}
int arrInversion(int arr[], int n) {
    int temp[n];
    return mergeSort(arr, temp, 0, n - 1);
}
int main() {
    int arr[] = {1, 5, 6, 4, 20};
    int n = 5;
    cout << "Number of inversions are " << arrInversion(arr, n);
}

出力結果

Number of inversions are 2

実行すると、転倒数として「2」が出力されます。

計算量について

このアルゴリズムの時間計算量はO(n log n)です。配列を再帰的に半分に分割する処理がO(log n)段階で行われ、各段階で全体のマージ処理にO(n)かかるためです。全ペアを総当たりで調べるO(n²)の素朴な手法と比べ、要素数が多い配列でも大幅に高速に動作します。