ソーティングネットワーク

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
四本のワイヤと五つのコンパレータからなる、単純なソーティングネットワーク

ソーティングネットワーク: sorting network)とは、ワイヤとコンパレータからなる、数列をソートするネットワーク(抽象的な数理モデル)である。一つのコンパレータが二つのワイヤを繋ぎ、小さい方の値を一方に、大きい方の値を他方に出力する。これによって値のソートが行われる。比較ソートアルゴリズムとソーティングネットワークの主な違いは、比較の順序が、それまでの比較の結果によらずあらかじめ決まっていることである。このため、アルゴリズムを並列に実行することが容易である。モデルは単純だが、ソーティングネットワークの理論は非常に深く、複雑である。

概要[編集]

ソーティングネットワーク中のコンパレータの例

ソーティングネットワークは、ワイヤとコンパレータという二つの要素からなる。ワイヤは値を伝える。コンパレータは入出力に二本のワイヤを取り、二つの値が入力されると、小さい方の値を上のワイヤに、大きい方の値を下のワイヤに出力する。ワイヤとコンパレータからなるネットワークのうち、任意の入力を正しく昇順にソートするものをソーティングネットワークと呼ぶ。

以下に、単純なソーティングネットワークの動作の様子を示す。このソーティングネットワークがなぜ入力を正しくソートするかは簡単に理解することが出来る。最初の四つのコンパレータは、最大の値を一番下に、最小の値を一番上に移動させている。最後のコンパレータは、真ん中の二つの値を並べ替えている。

SimpleSortingNetworkFullOperation.svg

挿入・選択ネットワーク[編集]

「挿入」や「選択」によって、任意の大きさのソーティングネットワークを再帰的に構成することが出来る。大きさ n のソーティングネットワークがあるとき、ソートが済んだ部分に新たな値を「挿入」することで大きさ n+1 のソーティングネットワークを構成することが出来る。これは挿入ソートにあたる。また、まず入力から最小値を「選択」し、残りの値を再帰的にソートしてもよい。これはバブルソートにあたる。

再帰的に構成されたソーティングネットワーク。まず最大の値を一番下に移動させ、それから残りのワイヤをソートする。バブルソートにあたる
再帰的に構成されたソーティングネットワーク。まず上の n 本のワイヤをソートし、それから残りの値を挿入する。挿入ソートにあたる

この二つのソーティングネットワークの構造は非常によく似ている。同時に実行出来るコンパレータをまとめれば、実際には二つは同一のものであることが分かる。

バブルソートのネットワーク
挿入ソートのネットワーク
コンパレータの並列を許せば、二つのネットワークは同一である

効率的なネットワーク[編集]

挿入ソートのネットワークの段数は O(n) となり、実用的ではない。バッチャー奇偶マージソートen:Batcher odd-even mergesort)やバイトニックソートen:bitonic sort)、シェルソートといった、段数O((log n)2) (すなわち、全体のサイズは O(n (log n)2) )の単純なネットワークが存在し、実際によく用いられている。

0-1原理[編集]

挿入ソートやバブルソートのネットワークのように、簡単に正当性を示せるソーティングネットワークも存在するが、正当性が常に簡単に示せるとは限らない。n 本のワイヤからなるネットワークに対し、n! 通り全ての場合を試すには、(大きなネットワークでは特に)時間がかかる。しかし、いわゆる0-1原理(zero-one principle)によれば、実際には遥かに少ない試行で十分である。

0-1原理とは、「あるネットワークが0と1からなる 2^n 通りの数列全てをソートすることが出来れば、それは正当なソーティングネットワークである」というものである。0-1原理によって、ソーティングネットワークの正当性を確かめるのに必要な試行の回数は大幅に減る。0-1原理は、様々なソーティングネットワークを構成するためにも有用である。

0-1原理は、W. G. Bouriciusによって1954年に証明されたBouriciusの定理の特別な場合である。

最適なソート[編集]

ソーティングネットワークの効率は、サイズ(使われているコンパレータの数)や段数(入力から出力までの経路上にあるコンパレータの数の最大値)によって測ることが出来る。

発見者のAjtai(en:Miklós Ajtai)、Komlós(en:János Komlós (mathematician))、Szemerédi(en:Endre Szemerédi)にちなんでAKSネットワークと呼ばれるソーティングネットワークは、 n 個の入力に対して段数 O(log n) ・サイズ O(n log n) となる。これは漸近的に最適en:asymptotically optimal algorithm)である。また、このAKSネットワークを簡潔にしたものが後にPaterson(en:Mike Paterson)によって発表されている。AKSネットワークは重要な発見ではあるが、Big-O 記法に隠された巨大な定数があり、実用に供されることはほとんどない。この理由のひとつとしては、エキスパンダーグラフen:expander graph)の構成が挙げられる。小さな c に対してサイズ cn log n のソーティングネットワークを見つけるのは、依然として未解決問題のままである。

1個から8個までの入力に対しては最適なソーティングネットワークが知られており、それぞれ 0, 1, 3, 5, 9, 12, 16, 19 個のコンパレータを持つ (Knuth, 1997)。10個までの入力に対する最小の段数も知られており、それぞれ 0, 1, 3, 3, 5, 5, 6, 6, 7, 7 である。

参考文献[編集]

  • O. Angel, A.E. Holroyd, D. Romik, B. Virag, Random Sorting Networks, Adv. in Math., 215(2):839–868, 2007.
  • K.E. Batcher, Sorting networks and their applications, Proceedings of the AFIPS Spring Joint Computer Conference 32, 307–314 (1968).
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0-262-03293-7. Chapter 27: Sorting Networks, pp.704–724.
  • D.E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.4: Networks for Sorting, pp. 219–247.
  • Ajtai, M.; Komlós, J.; Szemerédi, E. (1983), “An O(n log n) sorting network”, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp. 1–9, doi:10.1145/800061.808726 .
  • M. S. Paterson, Improved sorting networks with O(log N) depth, Algorithmica 5 (1990), no. 1, pp. 75–92, doi:10.1007/BF01840378.

外部リンク[編集]