Pythonで配列の反転数（転倒数）をカウントする方法

はじめに

この記事では、配列内の反転（インバージョン）をカウントする問題とその解決策について詳しく解説します。

問題定義

問題： リストが与えられたとき、その中に含まれる反転の数をカウントして表示します。

反転数とは、配列を昇順にソートされた状態にするために必要な入れ替え（スワップ）の回数を表す指標です。具体的には、i < j かつ arr[i] > arr[j] を満たす要素のペア（i, j）の総数として定義されます。

実装例

# 反転数をカウントする関数
def InvCount(arr, n):
    inv_count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if (arr[i] > arr[j]):
                inv_count += 1
    return inv_count

# ドライバーコード
arr = [1, 5, 3, 8, 7]
n = len(arr)
print("Total number of inversions are:", InvCount(arr, n))

出力結果

Total number of inversions are: 2

コードの解説

このプログラムでは、外側のループで各要素を順番に取り出し、内側のループでそれ以降のすべての要素と比較しています。arr[i] > arr[j]（前方の要素が後方の要素より大きい）という条件を満たすたびに、カウンター inv_count を1ずつ増加させていきます。

上記の例では、配列 [1, 5, 3, 8, 7] の場合、「5と3」「8と7」の2組が反転ペアに該当するため、出力結果は「2」となります。

なお、使用されているすべての変数はローカルスコープ内で宣言されており、関数の外部から参照されることはありません。

計算量について

このアプローチは二重ループを使用しているため、時間計算量は O(n²) となります。配列のサイズが大きくなるほど処理時間が増加するため、大規模なデータを扱う場合は、マージソートを応用した O(n log n) のアルゴリズムを採用すると効率的に反転数を求められます。

まとめ

この記事では、Pythonを使って配列内の反転数をカウントするプログラムの作成方法について学びました。二重ループによるシンプルな実装は非常に理解しやすく、小規模なデータセットに対しては十分実用的な手法です。ぜひ実際にコードを実行して、動作を確認してみてください。