ネットワークの並べ替え - どのネットワークが比較をスキップできますか？

Question

GCCのqsortの実装では、中央値3を使用してピボットを選択します。その間、3つの要素はソートネットワークでソートされます。

3要素のソートネットワークでは、通常3回の比較が必要です。

if(a[0] > a[1]) swap(a[0], a[1]); 
if(a[1] > a[2]) swap(a[1], a[2]); 
else goto jump; 
if(a[0] > a[1]) swap(a[0], a[1]); 
jump:; 

似た何かがn = 4...16（比較の知ら最小最適な数を持っているもの）とネットワークのために行うことができる。しかし、この特定の実装では、最後の比較は、前の比較に応じて、スキップすることができますか？もしそうなら、どのように見えますか？

UPDATE： これまでのところ、私は1つの比較をスキップできます一つの他のネットワークを、発見した：

// sorting network for 5 elements 
if (a[0] > a[1]) { SWAP(a[0], a[1]); } 
if (a[2] > a[3]) { SWAP(a[2], a[3]); } 

if (a[1] > a[3]) { SWAP(a[1], a[3]); } 
if (a[2] > a[4]) { SWAP(a[2], a[4]); } 

if (a[0] > a[2]) { SWAP(a[0], a[2]); } 
if (a[1] > a[4]) { SWAP(a[1], a[4]); } 

if (a[1] > a[2]) { SWAP(a[1], a[2]); } 
if (a[3] > a[4]) { SWAP(a[3], a[4]); } 
else { goto jump; } 

if (a[2] > a[3]) { SWAP(a[2], a[3]); } 
jump:; 

私は12345のすべての順列でこれをテストし、それが正確にそれらのすべてをソートします。最適ソーティングネットワークをともかく

Answer 1

は、次の画像のサイズの分類のネットワークを使用して、任意のサイズN +1のソーティングネットワークを作成する方法を示しN最後を置くN追加の比較を行います場所の要素（これは挿入ソートを一度ソートネットワークへの翻訳どのように動作するか、一般的です）：

画像は、要素N +1場合よりも、それはかなり明白になりすでに最大のものであれば、要素を比較した後にすべてのコンパレータをスキップすることができますnとn +1。基本的に、n最後のコンパレータがfalseを返したら、次のものはスキップします。物事の壮大な計画では、私はの比較をスキップすることが可能であると言いたいと思います。ソートネットワーク。

ソートアルゴリズムでこのような条件を設定すると、ソートネットワークではなくなり、ソートネットワークのメリットが失われます。適切に実装されても分岐予測の問題は発生しません。

できるだけ比較とスワップが少ない小規模なコレクションをソートするだけの場合は、ソートアルゴリズムのunroll every possible pathを実行してから、すべてのパスに対して最適な数の移動/スワップを実行できます。 4つの要素を上回って完全に維持されず、そのようなアルゴリズムを正当化するのに十分な高価な移動や比較演算を持つことはありません。