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

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

1. 概要
-----

ソーティングネットワークは、ワイヤとコンパレータという二つの要素からなる。ワイヤは値を伝える。コンパレータは入出力に二本のワイヤを取り、二つの値が入力されると、小さい方の値を上のワイヤに、大きい方の値を下のワイヤに出力する。ワイヤとコンパレータからなるネットワークのうち、任意の入力を正しく昇順にソートするものをソーティングネットワークと呼ぶ。以下に、単純なソーティングネットワークの動作の様子を示す。このソーティングネットワークがなぜ入力を正しくソートするかは簡単に理解することが出来る。最初の四つのコンパレータは、最大の値を一番下に、最小の値を一番上に移動させている。最後のコンパレータは、真ん中の二つの値を並べ替えている。

1.1. 挿入・選択ネットワーク
----------------

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

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



1.2. 効率的なネットワーク
---------------

挿入ソートのネットワークの段数は O となり、実用的ではない。バッチャー奇偶マージソートやバイトニックソート、シェルソートといった、段数O2) の単純なネットワークが存在し、実際によく用いられている。

1.3. 0-1原理
----------

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

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

この原理の証明の大枠は次の通り。

初めに、今、正当性を証明したいn本のワイヤからなるあるネットワークが、n個の数列//a//1, ..., //a////n//}}を入力された時、//b//1, ..., //b////n//}}と出力すると考える。 この時、この入力列に対して単調増加関数f}}を適用し、入力列を//f//, ..., //f//}}に変換しても、このネットワークの出力は//f//, ..., //f//}}の順となるはずである。 これを示すには、まずx}},y}}の2つの値が入力されるネットワークについて考える。 この入力列にf}}を適用し、対象のネットワークに入力すれば出力はmin, //f//) =}} //f//)}},max, //f//) =}} //f//)}}を満たす。これは、元の入力列と同じ順序を守っていることに他ならない。これを数学的帰納法によって拡張し、n本のワイヤについて証明できる。

このようにf}}によって出力の順番は保たれることを考えれば、今考えているネットワークがこの入力列を正しくソートできない時、同様に変換後の入力列//f//, ..., //f//}}も正しくソートできないはずである。 この対偶によって、単調増加関数f}}について//f//, ..., //f//}}が正しくソートできることを示すことができれば、元の入力列も正しくソートできることになる。 ここで、入力列//a//1, ..., //a////n//}}について、列中のいずれかの値より小さくなる値、つまりあるjに対して//ai// < //aj//}}となるようなiを選び、f}}を

とする。これは単調増加関数であるため上記の条件を満たし、かつ、変換後の入力列は0と1のみからなる。

以上より、0と1のみからなる数列が対象のネットワークで正しくソートできていることが示されていれば、任意の入力値に対しても正しくソートできることの証明となる。

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

2. 計算量と効率
---------

ソーティングネットワークの効率は

サイズ、コストとも
段数、ディレイともによって測ることが出来る。

2.1. 最適なソート
-----------

//AKSネットワーク//というソーティングネットワークは、 n 個の入力に対して段数 O ・サイズ O となる。これは漸近的に最適なアルゴリズムである。また、このAKSネットワークを簡潔にしたものが後にPatersonによって発表されている。AKSネットワークは重要な発見ではあるが、Big-O 記法に隠された巨大な定数があり、実用に供されることはほとんどない。この理由のひとつとしては、エキスパンダーグラフの構成が挙げられる。小さな //c// に対してサイズ //cn// log //n// のソーティングネットワークを見つけるのは、依然として未解決問題のままである。

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

3. 脚注
-----

4. 参考文献
-------

O. Angel, A.E. Holroyd, D. Romik, B. Virag, //[1]//, Adv. in Math., 215:839–868, 2007.
K.E. Batcher, //[2]//, Proceedings of the AFIPS Spring Joint Computer Conference 32, 307–314 .
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.
last1=Ajtai.
M. S. Paterson, //Improved sorting networks with O// //depth//, Algorithmica 5 , no. 1, pp. 75–92, 10.1007/BF01840378}}.

5. 外部リンク
--------

[3]
[4]
[5]
[6]