Seleccionar eficientemente la mediana y los elementos a su izquierda y derecha

Supongamos que tenemos un conjunto de codificadores. $S = \{ a_1,a_2,a_3,\ldots , a_N \}$ $N$

Cada codificador tiene una calificación de y el número de medallas de oro , que habían ganado hasta ahora. $R_i$ $E_i$

Una empresa de software quiere contratar exactamente tres codificadores para desarrollar una aplicación.

Para contratar a tres codificadores, desarrollaron la siguiente estrategia:

Primero organizan los codificadores en orden ascendente de calificaciones y orden descendente de medallas de oro.
De esta lista organizada, seleccionan los tres codificadores intermedios. Por ejemplo, si la lista organizada es seleccionan codificadores . $(a_5,a_2,a_3,a_1,a_4)$ $(a_2,a_3,a_1)$

Ahora tenemos que ayudar a la empresa escribiendo un programa para esta tarea.

Entrada:

La primera línea contiene , es decir, el número de codificadores. $N$

Luego, la segunda línea contiene las clasificaciones del th codificador. $R_i$ $i$

La tercera línea contiene el número de medallas de oro que el codificador empacó . $i$

Salida:

Muestre solo una línea que contenga la suma de las medallas de oro obtenidas por los tres codificadores que seleccionará la compañía.

algorithms algorithm-design Jack
fuente

Entonces, ¿los codificadores mejor calificados siempre ganan menos medallas? Si no, ¿qué orden estás usando para ordenar?

JeffE

Respuestas:

Se trata de un problema de seleccionar el -ésimo elemento más pequeño de la lista resuelto por una clase de algoritmos llamada la Selección Algoritmos . Existen algoritmos deterministas de selección de tiempo lineal para que su problema se pueda resolver en tiempo lineal seleccionando los elementos más pequeños º de la lista sin clasificar original. $k$ $n/2,n/2-1,n/2+1$

Optar
fuente

Si lo desea, puede ejecutar el algoritmo de selección una vez para encontrar la mediana, y luego encontrar el mínimo y el máximo en las particiones derecha e izquierda, respectivamente, de una sola vez.

Zach Langley

@Sid @ Zach Langley Hola, ¿puedes proporcionar el Pseudocódigo? I Pasé por la página wiki, pero se siente un poco difícil de entender. Entonces, ¿puedes proporcionar el Pseudocódigo? ¡Muchas gracias!

Jack

@ Jack, ¿estás familiarizado con cómo funciona Quicksort? El algoritmo de selección aleatoria es esencialmente el mismo, excepto que solo se repite en un lado de cada pivote.

Zach Langley

@Jack: El artículo de Wikipedia sobre algoritmos de selección (vinculado en la respuesta de Sid) contiene pseudocódigo. Google también funciona.

JeffE

@Sid :: Leí el algoritmo wiki (Algoritmo de selección general basado en particiones). ¿Tenemos que llamar a la función de selección tres veces con k = n / 2, k = n / 2-1, k / 2. También lo que será el valor de left, right mientras se llama a la función select.También en la función de partición, cuál será el valor del índice de partición.

Jack