バイトニックソート

バイトニックソート

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

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

このアルゴリズムはケン・バッチャー（英語: 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}}$）もしくはその循環シフトされたものである。

アルゴリズムの動作原理[編集]

バイトニックソートは比較と統合の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

表 話 編 歴 ソート
理論	計算複雑性理論 ランダウの記号 全順序 リスト 安定性 ソーティングネットワーク 比較ソート（英語版） 整数ソート（英語版）
交換ソート	バブルソート シェーカーソート 奇偶転置ソート コムソート ノームソート クイックソート
選択ソート	選択ソート ヒープソート スムースソート デカルト木ソート トーナメントソート
挿入ソート	挿入ソート シェルソート ツリーソート 図書館ソート ペイシェンスソート
マージソート	マージソート 多層マージソート ストランドソート
非比較ソート	基数ソート バケットソート 計数ソート プロキシマップソート 鳩の巣ソート バーストソート ビーズソート
並行ソート	バイトニックソート バッチャー奇偶マージソート シェアソート
混成ソート	ティムソート イントロソート Jソート アンシャッフルソート（英語版）
その他	トポロジカルソート パンケーキソート スパゲティソート
非効率的/ ユーモラスソート	ボゴソート ストゥージソート スリープソート エラーソート
カテゴリ