C++で配列をソートするのに必要な操作回数をカウントする方法

問題の概要

要素数n（nは奇数）の配列Aがあるとします。Aには、最初のn個の自然数（1〜n）の順列が格納されています。

ここで、0からn-2の範囲の引数iを1つ受け取る関数f(i)を考えます。この関数は、A[i] > A[i+1]である場合に、A[i]とA[i+1]の値を入れ替える操作を行います。

私たちの目的は、配列Aが初めて完全にソートされた状態になるまでに必要な反復回数を求めることです。

入出力例

例えば、入力が A = [4, 5, 7, 1, 3, 2, 6] の場合、出力は 5 になります。これは、各反復後に配列が次のように変化していくためです。

• [4, 5, 1, 7, 2, 3, 6]
• [4, 1, 5, 2, 7, 3, 6]
• [1, 4, 2, 5, 3, 7, 6]
• [1, 2, 4, 3, 5, 6, 7]
• [1, 2, 3, 4, 5, 6, 7]

解法のアプローチ

この問題は、いわゆる「奇偶交互ソート（Odd-Even Transposition Sort）」の考え方を利用して解くことができます。具体的な手順は以下の通りです。

1. 配列Aのサイズをnとし、反復回数を記録する変数Ansを0で初期化します。
2. まず配列全体を走査し、A[j] > A[j+1]となる箇所（未ソート部分）がまだ存在するかどうかをフラグfで確認します。
3. fが0（ソート完了）であれば、ループを抜けてAnsを返します。
4. そうでなければ、反復回数Ansの偶奇に応じて比較の開始位置を0または1に切り替え、jを2ずつ増やしながら隣接要素の比較・交換を実行します。
5. 1回の反復が終わるごとにAnsを1増やし、手順2に戻ります。

C++による実装例

それでは、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A){
    int n = A.size();
    bool f = 0;
    int Ans = 0;
    for (Ans = 0;;){
        // 未ソートの箇所が残っているか確認
        f = 0;
        for (int j = 0; j < n - 1; j++)
            if (A[j] > A[j + 1])
                f = 1;
        if (!f)
            break;
        // 偶奇に応じて開始位置を変えて隣接要素を交換
        for (int j = (Ans & 1); j < n - 1; j += 2)
            if (A[j] > A[j + 1])
                swap(A[j], A[j + 1]);
        Ans++;
    }
    return Ans;
}

int main(){
    vector<int> A = { 4, 5, 7, 1, 3, 2, 6 };
    cout << solve(A) << endl;
}

実行結果

入力

{ 4, 5, 7, 1, 3, 2, 6 }

出力

5

まとめ

このアルゴリズムは、各反復で偶数インデックスと奇数インデックスのペアを交互に処理する「奇偶交互ソート」をベースにしています。バブルソートと比べて並列化しやすいという特徴があり、計算量は最悪でO(n²)となりますが、実装がシンプルで動作の流れも追いやすいのが魅力です。ソート完了の判定を毎回の反復前に行うことで、余分な処理を省き、初めて整列した時点の反復回数を正確に取得できる点もポイントです。