質問者は、ソーティングネットワークに基づく中央値5の実装に特に関心があったので、この特定のケースに対処します。文献の簡単なレビューは、さまざまなメトリックに従って最適なソリューションがどのように見えるかを示しています。
Michael Codish、LuísCruz-Filipe、Thorsten Ehlers、MikeMüller、PeterSchneider-Kamp。「ネットワークの並べ替え:最後までやり直してください。」表1のJournalofComputer and System Sciences (2016)は、 n = 5の場合、コンペアスワップの最小数は9であり、ネットワークの最小深度は5であることを示しています。各コンペアスワップは2分に相当します。最大操作、必要な最小/最大操作の最小数は18です。
LukáŝSekanina、「中央回路のための革新的なデザインスペースの探索」。In:EvoWorkshops、2004年3月、240〜249ページでは、最適な5入力中央値選択ネットワークに必要な最小/最大操作の最小数を表1の10として示しています。
ウィリアム・ガサルチ、ウェイン・ケリー、ウィリアム・ピュー。「小さいi、nのnのi番目に大きいものを見つける。」ACM SIGACTニュース27、いいえ。2(1996):88-96、表1:中央値-5には、少なくとも6つの比較が必要です。
一般に、最小の操作数でネットワークをソートしても、冗長な操作を排除するだけでは、最小の操作数で中央値選択ネットワークになりません。しかし、 nの少なくともいくつかの値に対して最適な方法で減少するネットワークを見つけることは可能です。n = 5の場合、そのようなネットワークのブルートフォース検索が実行可能です。
以下のコードは、9つのコンペアスワップ操作または18分/最大操作を含む5入力ソーティングネットワークの4つのバリアントを示しています。これらを使用してコンパイルするとFULL_SORT = 0
、10分/最大操作の中央値選択ネットワークになります。したがって、このメトリックによれば、並べ替えと中央値の選択の両方が最適です。
ただし、ソーティングネットワークとして使用する場合、4つのバリアントすべての深さは最小5ではなく6になります。また、最小/最大操作ではなく比較に基づく中央値選択ネットワークとして構成されている場合、すべてが最小6回の比較ではなく7回の比較を必要とします。
コンパイラエクスプローラー(godbolt)からのコンパイル結果の例:5入力ソートに18分/最大操作を使用し、5入力中央値に10分/最大操作を使用します。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define VARIANT 1
#define USE_MIN_MAX 1
#define FULL_SORT 0
typedef float T;
#if USE_MIN_MAX
#define MIN(a,b) ((T)(fmin(a,b)))
#define MAX(a,b) ((T)(fmax(a,b)))
#define SWAP(i,j) do { T s = MIN(a##i,a##j); T t = MAX(a##i,a##j); a##i = s; a##j = t; } while (0)
#else // USE_MIN_MAX
#define MIN(a,b) (((a) > (b)) ? (b) : (a))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define SWAP(i,j) do { if (a##i > a##j) { T temp = a##i; a##i = a##j; a##j = temp; }} while (0)
#endif // USE_MIN_MAX
/* Use sorting/median network to fully or partially sort array of five values
and return the median value
*/
T network5 (T *a)
{
// copy to scalars
T a0, a1, a2, a3, a4;
a0=a[0];a1=a[1];a2=a[2];a3=a[3];a4=a[4];
#if VARIANT == 1
SWAP (0, 1); SWAP (2, 3);
SWAP (0, 2); SWAP (1, 3);
SWAP (2, 1);
SWAP (1, 4);
SWAP (1, 2);
SWAP (0, 1); SWAP (3, 4);
#elif VARIANT == 2
SWAP (3, 4); SWAP (0, 2);
SWAP (2, 4); SWAP (0, 3);
SWAP (2, 3);
SWAP (1, 2);
SWAP (0, 1); SWAP (2, 3);
SWAP (3, 4);
#elif VARIANT == 3
SWAP (3, 2); SWAP (0, 4);
SWAP (2, 4); SWAP (0, 3);
SWAP (2, 3);
SWAP (1, 2);
SWAP (0, 1); SWAP (2, 3);
SWAP (3, 4);
#elif VARIANT == 4
SWAP (2, 4); SWAP (0, 1);
SWAP (0, 2); SWAP (1, 4);
SWAP (2, 3);
SWAP (1, 2);
SWAP (2, 3); SWAP (0, 1);
SWAP (3, 4);
#else
#error unsupported VARIANT
#endif
#if FULL_SORT
// copy back sorted results
a[0]=a0;a[1]=a1;a[2]=a2;a[3]=a3;a[4]=a4;
#endif
// return median-of-5
return a2;
}