アルゴリズムの動作原理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/06/06 10:07 UTC 版)
「バイトニックソート」の記事における「アルゴリズムの動作原理」の解説
16要素のバイトニックソートのソーティングネットワーク図例。左端から値が入力され、右方向へ16本の水平なワイヤを通って、右端に出力される。この例では値の大きい要素が下に出力される。 矢印はコンパレータ（比較演算）表す。2つのワイヤ（＝値）が両端に到達したときに、その2つの値を比較し、矢印の方向に大きい値が出力される。 赤色の箱は比較の操作を表す。矢印の方向は暗い赤色が上、明るい赤が下向きである。暗い赤色の出力の上半分の要素は、必ず下半分のどの要素よりも値が小さいか等しくなる（暗い色では逆になる）。 青色と緑色の箱は統合の操作を表す。矢印の方向は青色が下、緑色が上向きである。青色の箱の出力では、下に大きな値がくるように並び替えられている（緑色では逆になる）。 バイトニックソートは比較と統合の2つの操作からなり、それぞれ入力列と出力列を持つ。 比較の操作では、入力列の上半分が下半分と決められた同じ方向に比較される。もし入力がバイトニック列であれば、出力は上半分と下半分がそれぞれバイトニック列になり、かつ、上半分の各要素の値は下半分のどの点の値より小さいか等しくなるもしくはその逆のはずである。この法則は、0と1のみからなるバイトニック列には0,1または1,0の列が2つ以上ないことを考えれば、0-1原理を用いて確認することができる。 統合の操作では、入力列に対して、比較の操作を上半分と下半分に分割して適用し、さらにそれぞれを上下分割することを繰り返すバタフライネットワーク（英語: butterfly network）となっている。入力列がバイトニック列であれば、出力列は比較の方向に従って全体の並び替えが完了する。なぜなら、先述の通り比較操作では出力の上半分が下半分より大きい（または小さい）ようになるため、上半分と下半分をさらに比較の操作を適用することで、各四分割された列がそれぞれ順に並ぶ。これを最小単位まで繰り返すことで、全体の並び替えが達成されるのである。 ソーティングネットワーク全体は、この統合の操作によって構成されている。並び替えの方向を逆にした統合の操作を交互に並べることで、それらの出力を結合した倍の長さの列は、バイトニック列となる。最初は2要素の入力（自明なバイトニック列）から開始され、全体が1つに統合されるまで繰り返し適用される。
※この「アルゴリズムの動作原理」の解説は、「バイトニックソート」の解説の一部です。
「アルゴリズムの動作原理」を含む「バイトニックソート」の記事については、「バイトニックソート」の概要を参照ください。
- アルゴリズムの動作原理のページへのリンク
