El solicitante estaba específicamente interesado en una implementación de la mediana de 5 basada en redes de clasificación, por lo que abordaré este caso específico. Una breve revisión de la literatura indica cuáles son las soluciones óptimas de acuerdo con varias métricas.
Michael Codish, Luís Cruz-Filipe, Thorsten Ehlers, Mike Müller y Peter Schneider-Kamp. "Ordenando redes: hasta el final y viceversa". Journal of Computer and System Sciences (2016) en la tabla 1 muestra que para n = 5, el número mínimo de compare-swaps es 9, y la profundidad mínima de la red es 5. Como cada comparación-swap es equivalente para dos operaciones mín./máx., , la cantidad mínima de operaciones mínima/máxima requerida es 18.
Lukáŝ Sekanina, "Exploración espacial de diseño evolutivo para circuitos medianos". En:. EvoWorkshops, marzo de 2004, pp 240-249, da el número mínimo de operaciones mín/máx necesarios para una óptima red de selección de mediana de cinco entradas como 10 en la tabla 1.
William Gasarch, Wayne Kelly y William Pugh. "Encontrar el i-ésimo mayor de n para pequeño i, n." ACM SIGACT News 27, no. 2 (1996): 88-96, tabla 1: se necesitan al menos 6 comparaciones para la mediana de 5.
En general, la clasificación de redes con el número mínimo de operaciones es no se reduce a redes de selección mediana con el número mínimo de operaciones simplemente mediante la eliminación de operaciones redundantes. Pero es posible encontrar redes que se reducen de manera óptima por al menos algunos valores de n. Para n = 5, es factible una búsqueda de fuerza bruta para tales redes.
El siguiente código muestra cuatro variantes de redes de clasificación de cinco entradas que comprenden 9 operaciones de cambio de comparación u, alternativamente, 18 operaciones de mín/máx. Cuando se compila con FULL_SORT = 0, estos se convierten en redes de selección mediana con operaciones de 10 min/max. De acuerdo con esta métrica, tanto la clasificación como la selección de la mediana son óptimas.
Pero, cuando se utiliza como una red de clasificación, las cuatro variantes tienen una profundidad de seis en lugar de un mínimo de cinco. Además, cuando se configura como una red de selección de medios basada en comparaciones en lugar de operaciones mín/máx, todas requieren siete en lugar de seis comparaciones como mínimo.
Ejemplo de resultados de compilación del compilador Explorer (godbolt): usando operaciones de 18 min/max para cinco entradas sort, usando operaciones de 10 min/max para cinco entradas median.
#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 (1, 2); SWAP (4, 3);
SWAP (2, 3);
SWAP (0, 2); SWAP (1, 4);
SWAP (2, 4);
SWAP (3, 4); SWAP (0, 2);
SWAP (0, 1);
#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;
}
¿Están vinculados los valores de los n elementos o son valores arbitrarios? – JoshD
Son objetos opacos en los que se comparan y se intercambian las únicas operaciones, pero dado que 'n' es pequeño, una buena implementación sería usar una matriz de punteros/índices y realizar los intercambios en la matriz de punteros. –
en lo que creo que estaba llegando JoshD, ¿son los valores _astronómicamente_ grandes, como valores con 10^999 números en ellos? De su respuesta, supongo que no, pero la pregunta es inteligente. –