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

四本のワイヤと五つのコンパレータからなる、単純なソーティングネットワーク

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

概要

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

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

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

挿入・選択ネットワーク

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

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

再帰的に構成されたソーティングネットワーク。まず上の n 本のワイヤをソートし、それから残りの値を挿入する。挿入ソートにあたる

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

バブルソートのネットワーク

挿入ソートのネットワーク

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

効率的なネットワーク

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

0-1原理

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

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

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

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

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

$f(x)={\begin{cases}1\ &{\mbox{if }}x>a_{i}\\0\ &{\mbox{otherwise.}}\end{cases}}$

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

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

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

計算量と効率

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

• サイズ（使われているコンパレータの数）、コストとも
• 段数（並列実行できない＝逐次実行しないといけないコンパレータの数、入力から出力までの経路上にあるコンパレータの数の最大値）、ディレイ(delay)とも

によって測ることが出来る。

最適なソート

AKSネットワーク（発見者のAjtai（en:Miklós Ajtai）、Komlós（en:János Komlós (mathematician)）、Szemerédi（en:Endre Szemerédi）にちなむ）というソーティングネットワークは、 n 個の入力に対して段数 O(log n) ・サイズ O(n log n) となる。これは漸近的に最適なアルゴリズム（英語: 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.

外部リンク

• Sorting Networks（英語）
• Sorting Networks（英語）
• List of Sorting Networks（英語）
• Sorting networks and the END algorithm（英語）