Il richiedente è stato specificamente interessato a un'implementazione mediana di 5 basata su reti di smistamento, quindi affronterò questo caso specifico. Una breve rassegna della letteratura indica quali sono le soluzioni ottimali in base alle varie metriche.
Michael Codish, Luís Cruz-Filipe, Thorsten Ehlers, Mike Müller e Peter Schneider-Kamp. "Ordinamento delle reti: fino alla fine e viceversa." Journal of Computer and System Sciences (2016) nella tabella 1 mostra che per n = 5, il numero minimo di confronti-swap è 9 e la profondità minima della rete è 5. Come ogni confronto-swap è equivalente a due operazioni min/max, il numero minimo di operazioni min/max richieste è 18.
Lukáŝ Sekanina, "Esplorazione spaziale del design evolutivo per i circuiti mediani". In:. EvoWorkshops, marzo 2004, pp 240-249, dà il numero minimo di min/max operazioni necessarie per una rete mediana-selezione di cinque ingressi ottimale come 10 nella tabella 1.
William Gasarch, Wayne Kelly e William Pugh. "Trovare il più grande di n per i piccoli, n". ACM SIGACT News 27, n. 2 (1996): 88-96, tabella 1: sono necessari almeno 6 confronti per la mediana di 5.
In generale, lo smistamento delle reti con il numero minimo di operazioni è non ridurre a reti di selezione mediana con il numero minimo di operazioni semplicemente mediante l'eliminazione di operazioni ridondanti. Ma è possibile trovare reti che si riducono in modo ottimale per almeno alcuni valori di n. Per n = 5, una ricerca forza bruta per tali reti è fattibile.
Il codice seguente mostra quattro varianti di reti di smistamento a cinque ingressi comprendenti 9 operazioni di confronto-scambio o, in alternativa, 18 operazioni min/max. Se compilati con FULL_SORT = 0 questi si trasformano in reti di selezione mediana con operazioni di 10 min/max. Quindi, secondo questa metrica, sia l'ordinamento che la selezione mediana sono ottimali.
Tuttavia, se utilizzato come rete di smistamento, tutte e quattro le varianti hanno una profondità di sei anziché il minimo di cinque. Inoltre, quando configurato come rete di selezione dei media basata su confronti invece di operazioni min/max, tutti richiedono sette anziché il minimo di sei confronti.
Esempio di compilazione dei risultati da Compiler Explorer (Godbolt): Utilizzo di 18 min/max operazioni per cinque ingressi sort, utilizzando 10 min/max operazioni per cinque ingressi 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;
}
I valori degli n elementi sono vincolati o sono valori arbitrari? – JoshD
Sono oggetti opachi su cui le sole operazioni sono confrontabili e scambiate, ma dato che 'n' è piccolo, una buona implementazione sarebbe usare una serie di puntatori/indici ed eseguire gli swap nell'array puntatore. –
quello che penso JoshD stava ottenendo, sono i valori _astronomicamente_ grandi, come vales con 10^999 numeri in loro? Dalla tua risposta credo di no, ma la domanda è intelligente. –