trovando mediana di 5 elementi

Question

la seguente domanda è stata posta in una recente intervista Microsoft

Dato un array non ordinato di dimensione 5. Quanti confronti minimo sono necessari per trovare la mediana? poi lo ha esteso per la dimensione n.

soluzione per 5 elementi secondo me è 6

1) use 3 comparisons to arrange elements in array such that a[1]<a[2] , a[4]<a[5] and a[1]<a[4] 
a) compare a[1] and a[2] and swap if necessary 
b) compare a[4] and a[5] and swap if necessary 
c) compare a[1] and a[4].if a[4] is smaller than a[1] , then swap a[1] wid a[4] and a[2] wid a[5] 
2)if a[3]>a[2].if a[2]<a[4] median value = min(a[3],a[4]) else median value=min(a[2],a[5]) 
3)if a[3]<a[2].if a[3]>a[4] median value = min(a[3],a[5]) else median value=min(a[2],a[4]) 

può questo essere esteso ad n elementi. in caso contrario, come è possibile trovare la mediana in n elementi in O (n) oltre a quickselect

Answer 1

L'algoritmo Select divide l'elenco in gruppi di cinque elementi. (Gli elementi sinistri vengono ignorati per ora.) Quindi, per ogni gruppo di cinque, viene calcolata la mediana (un'operazione che può potenzialmente essere fatta molto velocemente se i cinque valori possono essere caricati in registri e confrontati - 6 confronti min). Select viene quindi chiamato ricorsivamente su questa sottolista di n/5 elementi per trovare la loro vera mediana.