バイトニックソート

バイトニックマージソート（英語: Bitonic mergesort）または単にバイトニックソート（英語: Bitonic sort）とは、ソートの並列アルゴリズムの１つ。ソーティングネットワークの構築法としても知られている。

バイトニックソート

8要素のバイトニックソートネットワーク
クラス	ソート
データ構造	配列
最悪計算時間	${\displaystyle O(\log ^{2}(n))}$（並列実行の場合）
最良計算時間	${\displaystyle O(\log ^{2}(n))}$（並列実行の場合）
平均計算時間	${\displaystyle O(\log ^{2}(n))}$（並列実行の場合）
最悪空間計算量	${\displaystyle O(n\log ^{2}(n))}$（非並列実行の場合）

このアルゴリズムはケン・バッチャー（英語: Ken Batcher）によって考案されたもので、このソーティングネットワークの計算量は${\displaystyle n}$個の要素に対して、サイズ（コンパレータ数＝比較演算の回数）は${\displaystyle O(n\log ^{2}(n))}$、段数（並列実行不可能な数）は${\displaystyle O(\log ^{2}(n))}$となる^[1]。各段での比較演算（n/2回）は独立して実行できるため、並列化による高速化が容易である。

バイトニックソートでは、バイトニック列（英語: bitonic sequence）を生成しながら並べ替えを実行する。このバイトニック列は、単調非増加の後に単調非減少となるかその逆である列のことである。つまり、k個目までは昇順でそれ以降は降順（つまり、${\displaystyle 0\leq k<n}$に対して${\displaystyle x_{0}\leq \cdots \leq x_{k}\geq \cdots \geq x_{n-1}}$）もしくはその循環シフトされたものである。

アルゴリズムの動作原理

16要素のバイトニックソートのソーティングネットワーク図例。左端から値が入力され、右方向へ16本の水平なワイヤを通って、右端に出力される。この例では値の大きい要素が下に出力される。

• 矢印はコンパレータ（比較演算）表す。2つのワイヤ（＝値）が両端に到達したときに、その2つの値を比較し、矢印の方向に大きい値が出力される。
• 赤色の箱は比較の操作を表す。矢印の方向は暗い赤色が上、明るい赤が下向きである。暗い赤色の出力の上半分の要素は、必ず下半分のどの要素よりも値が小さいか等しくなる（暗い色では逆になる）。
• 青色と緑色の箱は統合の操作を表す。矢印の方向は青色が下、緑色が上向きである。青色の箱の出力では、下に大きな値がくるように並べ替えられている（緑色では逆になる）。

バイトニックソートは比較と統合の2つの操作からなり、それぞれ入力列と出力列を持つ。

比較の操作では、入力列の上半分が下半分と決められた同じ方向に比較される。 もし入力がバイトニック列であれば、出力は上半分と下半分がそれぞれバイトニック列になり、かつ、上半分の各要素の値は下半分のどの点の値より小さいか等しくなるもしくはその逆のはずである。この法則は、0と1のみからなるバイトニック列には0,1または1,0の列が2つ以上ないことを考えれば、0-1原理を用いて確認することができる。

統合の操作では、入力列に対して、比較の操作を上半分と下半分に分割して適用し、さらにそれぞれを上下分割することを繰り返すバタフライネットワーク（英語: butterfly network）となっている。 入力列がバイトニック列であれば、出力列は比較の方向に従って全体の並べ替えが完了する。なぜなら、先述の通り比較操作では出力の上半分が下半分より大きい（または小さい）ようになるため、上半分と下半分をさらに比較の操作を適用することで、各四分割された列がそれぞれ順に並ぶ。これを最小単位まで繰り返すことで、全体の並べ替えが達成されるのである。

ソーティングネットワーク全体は、この統合の操作によって構成されている。並べ替えの方向を逆にした統合の操作を交互に並べることで、それらの出力を結合した倍の長さの列は、バイトニック列となる。最初は2要素の入力（自明なバイトニック列）から開始され、全体が1つに統合されるまで繰り返し適用される。

別の表現方法

矢印が必要のない（比較の方向が揃った）バイトニックソートのネットワーク例。オレンジ色の箱が、新しく定義された「入力の下半分だけを上下反転させてからの比較操作」

先述の表現では、比較の操作において方向を変化させるような方法で説明した。 しかし、比較の方向を同じに揃える表現も可能である。

そのために、入力の下半分だけを上下反転させてから通常の比較操作をする新しい操作を定義する。 そして、先述の方法から、各統合の操作の最初の比較操作を、この操作に置き換える。

こうすると、並べ替えの方向は全て同じにすることができるため、この表現方法が、バイトニックソートの最も普遍的な表現方法となる。

実装例

以下に、再帰呼び出しを用いたPythonを用いたバイトニックソートの実装例を示す。入力は、論理値upと2べき乗個の配列xであり、出力は、upが真であれば昇順、でなければ降順となる。

def bitonic_sort(up: bool, x: Sequence[int]) -> List[int]:
    """バイトニックソート

    引数:
      up: 真であれば昇順、偽であれば降順
      x: 整数列

    Returns:
      upに従って並べ替えられた整数列
    """
    if len(x) <= 1:
        return x
    else: 
        first = bitonic_sort(True, x[:len(x) // 2])
        second = bitonic_sort(False, x[len(x) // 2:])
        return bitonic_merge(up, first + second)

def bitonic_merge(up: bool, x) -> List[int]: 
    # 入力xがバイトニック列であれば、並べ替えられて出力される
    if len(x) == 1:
        return x
    else:
        bitonic_compare(up, x)
        first = bitonic_merge(up, x[:len(x) // 2])
        second = bitonic_merge(up, x[len(x) // 2:])
        return first + second

def bitonic_compare(up: bool, x) -> None:
    dist = len(x) // 2
    for i in range(dist):
        if (x[i] > x[i + dist]) == up:
            x[i], x[i + dist] = x[i + dist], x[i]  # 交換

>>> bitonic_sort(True, [10, 30, 11, 20, 4, 330, 21, 110])
[4, 10, 11, 20, 21, 30, 110, 330]
>>> bitonic_sort(False, [10, 30, 11, 20, 4, 330, 21, 110])
[330, 110, 30, 21, 20, 11, 10, 4]

再帰呼び出しを用いない例（Javaによる）は以下のようになる。

public class BitonicSort {
    static void kernel(int[] a, final int p, final int q) {
        final int d = 1 << (p-q);

        for (int i = 0; i < a.length; i++) {
            boolean up = ((i >> p) & 2) == 0;

            if ((i & d) == 0 && (a[i] > a[i | d]) == up) {
                int t = a[i];
                a[i] = a[i | d];
                a[i | d] = t;
            }
        }
    }

    static void bitonicSort(final int logn, int[] a) {
        assert a.length == 1 << logn;

        for (int i = 0; i < logn; i++) {
            for(int j = 0; j <= i; j++) {
                kernel(a, i, j);
            }
        }
    }

    public static void main(String[] args) {
        final int logn = 5, n = 1 << logn;

        int[] a0 = new int[n];
        for (int i = 0; i < n; i++) {
            a0[i] = (int)(Math.random() * 1000);
        }

        for (int k = 0; k < a0.length; k++) {
            System.out.print(a0[k] + " ");
        }
        System.out.println();

        bitonicSort(logn, a0);

        for (int k = 0; k < a0.length; k++) {
            System.out.print(a0[k] + " ");
        }
        System.out.println();
    }
}

脚注

1. Bitonic sorting network for n not a power of 2

関連項目

• バッチャー奇偶マージソート

外部リンク

• A discussion of this algorithm
• Reference code at NIST
• Tutorial with animated pictures and working code