バイトニックソートのソースを表示

{{Infobox Algorithm
|class=[[ソート]]
|image=[[File:Batcher Bitonic Mergesort for eight inputs.svg|8要素のバイトニックソートネットワーク]]
|caption=8要素のバイトニック[[ソーティングネットワーク|ソートネットワーク]]
|data=[[配列]]
|best-time= <math>O(\log^2(n))</math>（並列実行の場合）
|average-time= <math>O(\log^2(n))</math>（並列実行の場合）
|time=<math>O(\log^2(n))</math>（並列実行の場合）
|space=<math>O(n \log^2(n))</math>（非並列実行の場合）
}}

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

このアルゴリズムは{{日本語版にない記事リンク|ケン・バッチャー|en|Ken Batcher}}によって考案されたもので、このソーティングネットワークの計算量は<math>n</math>個の要素に対して、サイズ（コンパレータ数＝比較演算の回数）は<math>O(n\log^2(n))</math>、段数（並列実行不可能な数）は<math>O(\log^2(n))</math>となる<ref>[http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/oddn.htm Bitonic sorting network for n not a power of 2<!-- Bot generated title -->]</ref>。各段での比較演算（n/2回）は独立して実行できるため、[[並列化]]による高速化が容易である。

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

== アルゴリズムの動作原理 ==

[[File:bitonicSort1.svg|frame|center|16要素のバイトニックソートの[[ソーティングネットワーク]]図例。左端から値が入力され、右方向へ16本の水平なワイヤを通って、右端に出力される。この例では値の大きい要素が下に出力される。{{ul
|矢印はコンパレータ（比較演算）表す。2つのワイヤ（＝値）が両端に到達したときに、その2つの値を比較し、矢印の方向に大きい値が出力される。
|赤色の箱は比較の操作を表す。矢印の方向は暗い赤色が上、明るい赤が下向きである。暗い赤色の出力の上半分の要素は、必ず下半分のどの要素よりも値が小さいか等しくなる（暗い色では逆になる）。
|青色と緑色の箱は統合の操作を表す。矢印の方向は青色が下、緑色が上向きである。青色の箱の出力では、下に大きな値がくるように並べ替えられている（緑色では逆になる）。
}}]]

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

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

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

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

=== 別の表現方法 ===

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

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

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

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

== 実装例 ==
以下に、[[再帰呼び出し]]を用いた[[Python]]を用いたバイトニックソートの実装例を示す。入力は、論理値''up''と2べき乗個の配列''x''であり、出力は、''up''が真であれば昇順、でなければ降順となる。
<syntaxhighlight lang="python">
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]  # 交換
</syntaxhighlight>

<syntaxhighlight lang="pycon">
>>> 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]
</syntaxhighlight>

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

<syntaxhighlight lang="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();
    }
}
</syntaxhighlight>

== 脚注 ==
<References />

== 関連項目 ==
* [[バッチャー奇偶マージソート]]

== 外部リンク ==
*[http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm A discussion of this algorithm]
*[https://xlinux.nist.gov/dads/HTML/bitonicSort.html Reference code] at [[NIST]]
*[http://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm Tutorial with animated pictures and working code]

{{ソート}}

{{DEFAULTSORT:はいとにくそおと}}
[[Category:ソート]]