hallazgo se preguntó mediana de 5 elementos

Question

la siguiente pregunta en una entrevista reciente Microsoft

Dado un vector que no clasificada de tamaño 5. ¿Cuántas comparaciones mínimo son necesarios para encontrar la mediana? luego lo extendió para el tamaño n.

solución

para 5 elementos según me es 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]) 

puede esta ampliarse a n elementos. si no, ¿cómo podemos encontrar la mediana en n elementos en O (n) además de quickselect

Answer 1

El algoritmo Select divide la lista en grupos de cinco elementos. (Los elementos restantes se ignoran por ahora). Luego, para cada grupo de cinco, se calcula la mediana (una operación que puede hacerse muy rápida si los cinco valores se pueden cargar en los registros y comparar: 6 comparaciones mínimas). Seleccionar se llama de forma recursiva en esta sublista de n/5 elementos para encontrar su mediana verdadera.