マージソートを使って配列の転倒数（反転数）を数えるC/C++プログラム

転倒数（Inversion Count）とは？

与えられた配列をソートする際に発生する反転（転倒）の回数を「転倒数（Inversion Count）」と呼びます。転倒数を求める問題は古典的なアルゴリズム問題の一つで、マージソート（Merge Sort）のアルゴリズムを応用することで効率的に解くことができます。

この問題では、各要素について「自分より左側にあり、かつ自分より大きな値を持つ要素」の数をすべて数え上げ、その合計を出力します。この処理は、マージソートのマージ（merge）関数の中で実装されます。

理解を深めるために、マージ処理で扱う2つの部分配列を例に考えてみましょう。

配列の転倒数の定義

配列が与えられたとき、その配列の転倒数を求めます。条件 (i < j) かつ (A[i] > A[j]) を満たすペア (i, j) を、配列 A の「転倒（inversion）」と呼びます。つまり、配列内に存在するこのようなペアをすべて数える必要があります。

例として、次の入力を考えてみます。

入力: arr[] = { 1, 9, 6, 4, 5 }
出力: 転倒数は 5

この配列には、次の5つの転倒ペアが存在します。

• (9, 6)
• (9, 4)
• (9, 5)
• (6, 4)
• (6, 5)

アルゴリズムの手順

1. 配列内の要素同士を比較します。
2. 小さいインデックス側の値が大きい場合、カウンターを増加させます。
3. 最終的な結果を表示します。

マージソートを利用するメリットは、計算量を素朴な全ペア比較（O(n²)）から O(n log n) に改善できる点です。マージ処理の際、右側の部分配列から要素が先に取り出されるとき、左側の部分配列に残っている要素の数だけ転倒が発生していることになります。これを inversionCount += (mid - i + 1) で一括して加算することで、効率的にカウントできます。

C言語による実装例

以下は、マージソートを用いて転倒数をカウントするC言語のサンプルコードです。

#include <stdio.h>

int Merge(int arr[], int aux[], int low, int mid, int high) {
    int k = low, i = low, j = mid + 1;
    int inversionCount = 0;

    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {
            aux[k++] = arr[i++];
        } else {
            aux[k++] = arr[j++];
            inversionCount += (mid - i + 1); // 転倒数を加算
        }
    }

    while (i <= mid)
        aux[k++] = arr[i++];

    for (int i = low; i <= high; i++)
        arr[i] = aux[i];

    return inversionCount;
}

int MergeSort(int arr[], int aux[], int low, int high) {
    if (high == low) // 要素数が1の場合
        return 0;

    int mid = (low + ((high - low) >> 1));
    int inversionCount = 0;

    inversionCount += MergeSort(arr, aux, low, mid);
    inversionCount += MergeSort(arr, aux, mid + 1, high);
    inversionCount += Merge(arr, aux, low, mid, high);

    return inversionCount;
}

int main() {
    int arr[] = { 1, 9, 6, 4, 5 };
    int N = 5;
    int aux[N];

    for (int i = 0; i < N; i++)
        aux[i] = arr[i];

    printf("Inversion count is %d", MergeSort(arr, aux, 0, N - 1));

    return 0;
}

実行結果

Inversion count is 5

まとめ

マージソートのマージ処理に転倒数のカウントを組み込むことで、配列の転倒数を O(n log n) の時間計算量で効率的に求めることができます。この手法は、配列が「どの程度ソートから離れているか」を測る指標としても活用されており、アルゴリズムの学習において重要な応用例の一つです。