ペアワイズソーティングネットワーク

ペアワイズソーティングネットワーク

16入力のペアワイズソートネットワークの視覚化
クラス	ソートアルゴリズム
データ構造	配列
最悪の場合の パフォーマンス	${\displaystyle (\log n)(\log n+1)/2}$パラレルタイム
最悪の場合の 空間複雑度	${\displaystyle n(\log n)(\log n-1)/4+n-1}$非平行時間
最適	いいえ

ペアワイズソーティングネットワークは、 1992 年に Ian Parberry が発見し、Parallel Processing Lettersで発表したソーティングネットワークです。^[1]ペアワイズソーティングネットワークは、奇数-偶数マージソートネットワークと同じサイズ (比較器の数) と深さを持ちます。発表時点では、このネットワークは深さ を持ついくつかの既知のネットワークの 1 つでした。このネットワークには比較器が必要で、深さ です。 ${\displaystyle O(\log^{2}n)}$${\displaystyle n(\log n)(\log n-1)/4+n-1}$${\displaystyle (\log n)(\log n+1)/2}$

ネットワークによって実装されるソート手順は次のとおりです（ゼロワン原則に従います）。

1. 入力の連続するペアビットをソートする（図の最初の層に対応）
2. すべての奇数ビットと偶数ビットを別々に再帰的にソートして、すべてのペアを辞書式順序にソートします（図の次の 14 層に対応します）。
3. 特殊なネットワークを使用して、ペアを非減少順に並べ替えます（図の最後のレイヤーに対応します）。

ペアワイズソートネットワークは、Batcher 奇偶マージソートと非常に似ていますが、操作の構造が異なります。Batcher は、徐々に長くなるサブシーケンスを繰り返し分割、ソート、マージしますが、ペアワイズ法では、最初にすべてのサブ分割を行い、最後に逆の順序ですべてのマージを行います。カーディナリティ制約のエンコードなどの特定のアプリケーションでは、ペアワイズソートネットワークは Batcher ネットワークよりも優れています。^[2]

• Sorting Networks – 著者による Web ページのアーカイブ。