C++で実装するバイトニックソート：並列処理に最適なソートアルゴリズムの解説

バイトニックソート（Bitonic Sort）は、ハードウェアや並列プロセッサアレイでの最適な実装を目的として設計された並列ソートアルゴリズムです。

マージソートなどと比較すると単体の効率は最高ではありませんが、比較順序があらかじめ定義されており、ソート対象のデータに依存せずに比較が行えるため、並列実行に非常に適しています。

また、バイトニックソートを効果的に機能させるには、要素数が2^n（2の累乗）である必要があるという特徴があります。

バイトニック列とは

バイトニックソートの中核をなすのが「バイトニック列（Bitonic Sequence）」です。これは、要素の値が最初は増加し、その後減少するような数列のことを指します。

具体的には、配列 arr[0 … (n-1)] において、あるインデックス i（0 ≤ i ≤ n-1）が存在し、arr[i] が配列内で最大値となっている場合、この配列はバイトニック列であるといえます。つまり以下の条件を満たします。

arr[0] <= arr[1] … <= arr[i] かつ arr[i] >= arr[i+1] … >= arr[n-1]

バイトニック列の特徴

• バイトニック列は回転させても、再びバイトニック列になります。

• 昇順部分と降順部分を持つ数列は、すべてバイトニック列です。

バイトニック列の作成方法

バイトニック列を作成するには、元の配列を「昇順の部分列」と「降順の部分列」の2つの部分列に分けて構成します。

例として、次の配列をバイトニック列に変換してみましょう。

arr[] = {3, 4, 1, 9, 2, 7, 5, 6}

ステップ1：まず要素をペアにし、交互に「昇順・降順」となるようにバイトニック列を作ります。

arr[] = {(3, 4), (1, 9), (2, 7), (5, 6)}
// バイトニック列のペアを作成…
arr[] = {(3, 4), (9, 1), (2, 7), (6, 5)}

ステップ2：次に、このペア同士を組み合わせて4要素のバイトニック列を作ります。距離2離れた要素同士（i 番目と i+2 番目）を比較します。

arr[] = {(3, 4, 9, 1), (2, 7, 6, 5)}

前半のセットは昇順のバイトニック列に変換します。

(3, 4, 9, 1) : 離れた要素同士を比較
(3, 1, 9, 4) : 次に隣接する要素を確認
(1, 3, 4, 9) → 昇順のバイトニック列が完成

後半のセットは降順のバイトニック列に変換します。

(2, 7, 6, 5) : 離れた要素同士を比較
(6, 7, 2, 5) : 次に隣接する要素を確認
(7, 6, 5, 2) → 降順のバイトニック列が完成

最終的に、サイズ8のバイトニック列が得られます。

1, 3, 4, 9, 7, 6, 5, 2

バイトニックソートの手順

バイトニック列について理解したところで、実際のソート手順を見ていきましょう。

ステップ1：バイトニック列を作成します。

ステップ2：この時点で、数列は昇順のパートと降順のパートに分かれています。

ステップ3：前半と後半の対応する要素同士（1番目同士、2番目同士…）を比較し、必要に応じて交換します。

ステップ4：次に、2つ隣の要素同士を比較して交換します。

ステップ5：最後に、隣接する要素同士を比較して交換します。

ステップ6：すべての交換が完了すると、ソート済みの配列が得られます。

C++による実装例

バイトニックソートを実装したプログラムは以下の通りです。

#include<iostream>
using namespace std;
void bitonicSeqMerge(int a[], int start, int BseqSize, int direction) {
    if (BseqSize>1){
        int k = BseqSize/2;
        for (int i=start; i<start+k; i++)
        if (direction==(a[i]>a[i+k]))
        swap(a[i],a[i+k]);
        bitonicSeqMerge(a, start, k, direction);
        bitonicSeqMerge(a, start+k, k, direction);
    }
}
void bitonicSortrec(int a[],int start, int BseqSize, int direction) {
    if (BseqSize>1){
        int k = BseqSize/2;
        bitonicSortrec(a, start, k, 1);
        bitonicSortrec(a, start+k, k, 0);
        bitonicSeqMerge(a,start, BseqSize, direction);
    }
}
void bitonicSort(int a[], int size, int up) {
    bitonicSortrec(a, 0, size, up);
}
int main() {
    int a[]= {5, 10, 51, 8, 1, 9, 6, 22};
    int size = sizeof(a)/sizeof(a[0]);
    printf("Original array: \n");
    for (int i=0; i<size; i++)
    printf("%d\t", a[i]);
    bitonicSort(a, size, 1);
    printf("\nSorted array: \n");
    for (int i=0; i<size; i++)
    printf("%d\t", a[i]);
    return 0;
}

実行結果

Original array:
5 10 51 8 1 9 6 22
Sorted array:
1 5 6 8 9 10 22 51

このように、バイトニックソートは再帰的にバイトニック列を構築しながらマージを行うことで、配列全体を整列させます。比較の順序がデータに依存しないため、GPUなどの並列アーキテクチャにおいて高い性能を発揮するアルゴリズムです。