ソーティングネットワーク ソーティングネットワークの概要

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/06/01 06:18 UTC 版)

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

概要

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

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

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

挿入・選択ネットワーク

「挿入」や「選択」によって、任意の大きさのソーティングネットワークを再帰的に構成することが出来る。大きさ 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 である。