C++で配列内の反転数（Inversion Count）を求めるプログラムの解説

「反転数（Inversion Count）」とは、配列を昇順にソートされた状態にするために必要な要素の入れ替え回数を表す指標です。配列がすでにソートされている場合、反転数は 0 となり、逆に配列が完全に逆順に並んでいる場合、反転数は最大値になります。

この記事では、配列内の反転数を数えるC++プログラムを実際に作成しながら、その考え方と実装方法をわかりやすく解説します。

反転数とは

配列内の2つの要素 a[i] と a[j] について、i < j かつ a[i] > a[j] が成り立つとき、このペアを「反転（inversion）」と呼びます。配列全体に存在する反転ペアの総数が反転数です。反転数が多いほど、配列はソートされた状態から遠いことになります。

アルゴリズム

ここでは最もシンプルな全ペア比較による方法（ブルートフォース）を用います。計算量は O(n²) ですが、アルゴリズムの理解には最適です。

Begin
    関数 CountInversionArray の引数：a[]（配列）、n（要素数）
    カウンタ c := 0 で初期化
    i を 0 から n-1 まで繰り返す：
        j を i+1 から n-1 まで繰り返す：
            もし a[i] > a[j] ならば
                c を 1 増やす
            j ループ終了
        i ループ終了
End.

サンプルコード

以下は、ユーザーから配列の要素を入力してもらい、反転数を出力する完全なC++プログラムです。

#include<iostream>
using namespace std;
int CountInversionArray(int a[], int n) {
    int i, j, c = 0;
    for(i = 0; i < n; i++) {
        for(j = i+1; j < n; j++)
            if(a[i] > a[j])
                c++;
    }
    return c;
}
int main() {
    int n, i;
    cout<<"\n要素数を入力してください: ";
    cin>>n;
    int a[n];
    for(i = 0; i < n; i++) {
        cout<<"要素 "<<i+1<<" を入力: ";
        cin>>a[i];
    }
    cout<<"\n配列内の反転数: "<<CountInversionArray(a, n);
    return 0;
}

実行結果

入力例として、5つの要素 {3, 2, 7, 6, 1} を与えた場合の実行結果は以下の通りです。

要素数を入力してください: 5
要素 1 を入力: 3
要素 2 を入力: 2
要素 3 を入力: 7
要素 4 を入力: 6
要素 5 を入力: 1

配列内の反転数: 6

処理の流れを確認

配列 {3, 2, 7, 6, 1} における反転ペアは次の6つです。

• (3, 2)
• (3, 1)
• (7, 6)
• (7, 1)
• (6, 1)
• (2, 1)

したがって、出力される反転数は 6 となります。

計算量と改善のポイント

上記のプログラムは二重ループを使用しているため、時間計算量は O(n²) です。要素数が多い場合は効率が悪くなります。より高速に反転数を求めたい場合は、マージソートを応用した O(n log n) のアルゴリズムや、Binary Indexed Tree（BIT）を使った手法が知られています。まずは本記事のシンプルな実装で基本概念をしっかり理解することをおすすめします。