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

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/04/20 13:20 UTC 版)

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

ソーティングネットワーク（英: 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!$ カテゴリ