Аскер был особенно заинтересован в реализации с медианой 5, основанной на сортировке сетей, поэтому я рассмотрю этот конкретный случай. Краткий обзор литературы показывает, как выглядят оптимальные решения по различным метрикам.
Майкл Кодиш, Луис Круз-Филипе, Торстен Элерс, Майк Мюллер и Питер Шнайдер-Камп. «Сортировка сетей: до конца и обратно». Журнал компьютерных и системных наук (2016) в таблице 1 показывает, что для n = 5 минимальное количество подкачек сравнения равно 9, а минимальная глубина сети равна 5 Так как каждый сравнение-своп эквивалентен двум мин / макс операциям,
минимальное количество требуемых операций min / max составляет 18.
Лукаш Секанина, "Эволюционное проектирование освоения космоса для срединных цепей". В: EvoWorkshops , март 2004 г., стр. 240-249, приведено минимальное количество операций min / max, необходимых для оптимальной сети с медианой выбора из пяти входов, равное 10 в таблице 1.
Уильям Гасарч, Уэйн Келли и Уильям Пью. «Нахождение i-го по величине из n для малого i, n.» ACM SIGACT News 27, нет. 2 (1996): 88-96, таблица 1:
по крайней мере 6 сравнений необходимы для медианы-5.
В общем случае, сети сортировки с минимальным количеством операций не сводятся к сетям с медианным выбором с минимальным количеством операций просто за счет исключения избыточных операций. Но можно найти сети, которые действительно уменьшают оптимальным образом по крайней мере для некоторых значений n . Для n = 5 возможен перебор для таких сетей.
Приведенный ниже код показывает четыре варианта сетей сортировки с пятью входами, включающих девять операций сравнения-обмена или, альтернативно, операции 18 мин / макс. При компиляции с FULL_SORT = 0 они превращаются в сети с медианным выбором с 10 мин / макс операциями. Таким образом, согласно этой метрике, сортировка и выбор медианы являются оптимальными.
Однако при использовании в качестве сортировочной сети все четыре варианта имеют глубину шесть, а не минимум пять. Кроме того, при настройке в качестве сети с медианным выбором на основе сравнений вместо операций min / max все требуют семи, а не шести сравнений.
Пример результатов компиляции из Compiler Explorer (godbolt): использование 18 мин / макс операций для пяти входов сортировка , использование 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;
}