C/C++による奇偶転置ソート（ブリックソート）の実装プログラム

ここでは、ブリックソート（Brick Sort／奇偶転置ソート）の仕組みについて詳しく解説します。ブリックソートは、バブルソートを改良したソートアルゴリズムの一つで、処理全体が「奇数フェーズ」と「偶数フェーズ」という2つのステップに分かれているのが特徴です。

奇数フェーズでは、奇数番目のインデックス（1, 3, 5, ...）にある要素同士を比較・交換し、偶数フェーズでは、偶数番目のインデックス（0, 2, 4, ...）にある要素同士を比較・交換します。この2つのフェーズを、配列全体がソート済みになるまで繰り返します。隣接する要素を独立して並列処理できるため、並列化に適したアルゴリズムとしても知られています。

アルゴリズム

brickSort(arr, n)

begin
    flag := false
    while the flag is not true, do
        flag := true
        for i := 1 to n-2, increase i by 2, do
            if arr[i] > arr[i+1], then
                exchange arr[i] and arr[i+1]
                flag := false
            end if
        done
        for i := 0 to n-2, increase i by 2, do
            if arr[i] > arr[i+1], then
                exchange arr[i] and arr[i+1]
                flag := false
            end if
        done
    done
end

このアルゴリズムでは、まずフラグ（flag）をfalseに初期化します。ループ内で一度でも要素の交換が発生した場合はフラグをfalseに戻し、交換が一切行われなかった場合のみフラグがtrueのままとなるため、そこでソート完了と判断できます。

実装例（C++）

#include<iostream>
using namespace std;
void brickSort(int arr[], int n){
    bool flag = false;
    while(!flag){
        flag = true;
        // 奇数フェーズ：奇数インデックスの要素を比較・交換
        for(int i = 1; i<n-1; i= i+2){
            if(arr[i] > arr[i+1]){
                swap(arr[i], arr[i+1]);
                flag = false;
            }
        }
        // 偶数フェーズ：偶数インデックスの要素を比較・交換
        for(int i = 0; i<n-1; i= i+2){
            if(arr[i] > arr[i+1]){
                swap(arr[i], arr[i+1]);
                flag = false;
            }
        }
    }
}
main() {
    int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
    int n = sizeof(data)/sizeof(data[0]);
    cout << "Sorted Sequence ";
    brickSort(data, n);
    for(int i = 0; i <n;i++){
        cout << data[i] << " ";
    }
}

実行結果

Sorted Sequence 13 20 32 35 40 54 74 98 98 154

このプログラムでは、初期データ {54, 74, 98, 154, 98, 32, 20, 13, 35, 40} を入力として与えると、奇数フェーズと偶数フェーズを交互に繰り返すことで、最終的に昇順にソートされた結果が出力されます。

計算量について

ブリックソートの計算量は、最悪ケース・平均ケースともにO(n²)であり、バブルソートと同程度です。一方で、各フェーズ内の比較・交換処理は互いに独立しているため、マルチスレッド環境やGPUなどでの並列処理に向いており、その点が通常のバブルソートと異なる大きな利点です。