奇偶転置ソート（ブリックソート）をC/C++で実装する方法

奇偶転置ソート（ブリックソート）は、バブルソートとよく似たソートアルゴリズムの一つです。この手法は「奇数フェーズ」と「偶数フェーズ」の2つのフェーズから構成されており、すべての要素が整列されるまで、各反復ごとに両方のフェーズが交互に実行されます。

奇数フェーズでは、バブルソートと同じ要領で比較と交換を行いますが、対象となるのは奇数番目のインデックスを持つ要素だけです。

同様に、偶数フェーズでは偶数番目のインデックスを持つ要素のみが処理されます。

概念をより分かりやすくするために、具体的な例を見てみましょう。

入力：a[]={3,5,7,6,1,4,2}
出力：1 2 3 4 5 6 7

アルゴリズムの解説

奇偶転置ソート（ブリックソート）は、並列処理を前提として設計されたシンプルなソート手法です。要素の整列には比較を使用し、隣接する奇数・偶数インデックスのペアごとに値を比較します。ペアの順序が誤っている場合は、それらを入れ替えて正しい順序にします。この処理をリスト全体が整列するまで繰り返します。

このアルゴリズムは並列コンピューティング向けに開発されたため、各プロセッサが1つの値を受け持ち、「比較と交換」の操作を複数のプロセッサが同時に実行できる点が大きな特徴です。元々はマルチプロセッサ環境で効率的に動作することを目的として提案されました。単一のプロセッサ上で実行した場合でも、平均計算量はO(n²)となり、バブルソートと同程度の性能を発揮します。

C言語による実装例

#include <stdio.h>
#include <math.h>
#define MAX 7
void swap(int *,int *);
void oddeven_sort(int *);
int main() {
    int a[]={3,5,7,6,1,4,2}, i;
    oddeven_sort(a);
    for (i = 0;i < MAX;i++) {
        printf(" %d", a[i]);
    }
}
void swap(int * x, int * y) {
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
void oddeven_sort(int * x) {
    int sort = 0, i;
    while (!sort) {
        sort = 1;
        for (i = 1;i < MAX;i += 2) {
            if (x[i] > x[i+1]) {
                swap(&x[i], &x[i+1]);
                sort = 0;
            }
        }
        for (i = 0;i < MAX - 1;i += 2) {
            if (x[i] > x[i + 1]) {
                swap(&x[i], &x[i + 1]);
                sort = 0;
            }
        }
    }
}

実行結果

1234567