Encuentre una mediana en paralelo

Question

Si tiene una gran cantidad de números y cien computadoras, ¿Cómo encontraría la mediana de los números?

Answer 1

Utilice el algoritmo de selección.

1. Divida la matriz de número en 100 particiones.
2. Cada procesador debe utilizar el pivote en general para dividir la matriz a dos grupos (izquierda/derecha)
3. continuación, cada procesador debe enviar el tamaño de esos 2 grupos al líder
4. el líder debe calcular qué grupo es menor y transmitir un mensaje para deshacerse de uno de esos grupos.
5. vuelva al paso 2 hasta que encuentre la mediana

esta solución tiene un tiempo de ejecución promedio de O (n) con el fin de hacer que el tiempo de ejecución asintótica de O (n), cada procesador debe dividir los números para grupos de 5 elementos, encuentre la mediana de cada grupo (utilizando ordenación por inserción) y envíe esas medianas al líder, el líder elegirá la mediana de esas medianas (utilizando el mismo algoritmo) y será el pivote

lea el artículo de la wiki - http://en.wikipedia.org/wiki/Selection_algorithm