example - quicksort algorithm

Quickselect Algorithm-Explicación simplificada

Question

He pedido esto antes HERE , sin embargo, deseo que la explicación de quickselect (basada en quicksort) se simplifique aún más. La pregunta anterior que le pedí incluía un código de ejemplo (para que sepa de qué estoy hablando).

Me preguntaba si alguien en algún lugar y en algún momento resumió las reglas y pautas de quickselect como un juego, donde uno puede aprender cómo funciona el algoritmo siguiendo reglas fáciles de entender que pueden aplicarse, digamos, un mazo de cartas o números en bits de papel.

Creo que una explicación simplificada del algoritmo de selección rápida sería primordial para mí entender cómo funciona, ya que aún los tutoriales y las explicaciones que he recibido son difíciles de comprender y visualizar. Incluso los videos en youtube que convierten el quicksort en un baile no han ayudado mucho.

Gracias de antemano Stack, has sido de gran ayuda hasta ahora.

Answer 1

Entras en un gimnasio que contiene 200 niños. Es el 8 de septiembre, por lo que tienes un deseo ardiente de encontrar el 98º niño más pequeño. Sabes que podrías alinearlos desde el más corto al más alto, pero eso llevaría una eternidad. "Lo sé", piensas, "¡Podría usar QUICKSELECT!"

Caminas hacia la multitud, cierras los ojos, sacas el dedo y das tres vueltas. Cuando abre los ojos, apunta directamente a uno de los niños, Peter Pivot. Usted dice: "¡Rápidamente! Todo el mundo es más bajo que Peter, párese aquí. Y todos los que sean más altos que Peter, párese allí. Si tiene la misma estatura que Peter, puede ir a cualquier grupo".

Los niños arrastran los pies, y pronto están parados en los dos grupos. Cuenta y encuentra 120 niños en el grupo más bajo y 79 niños en el grupo más alto. Usted sabe que el niño número 98 más bajo debe pertenecer al grupo más bajo, por lo que le dice a Peter y a los 79 niños más altos que se sienten en las gradas.

Cierra de nuevo los ojos, saca el dedo y gira tres veces. Cuando abres los ojos, estás señalando directamente a la hermana de Peter, Paula Pivot. Usted dice: "¡Rápidamente! Aquellos de ustedes que todavía están de pie. Si son más bajos que Paula, vengan aquí. Si son más altos que Paula, ve a pararte allí. Si tienes la misma altura, puedes entra en cualquier grupo ".

Los niños arrastran los pies, y pronto están parados en los dos grupos. Cuenta y encuentra 59 niños en el grupo más bajo y 60 niños en el grupo más alto. Usted sabe que el niño número 98 más bajo debe estar en el grupo más alto, por lo que le dice a Paula y los 59 niños más pequeños que se sienten en las gradas.

Cierra de nuevo los ojos, saca el dedo y gira tres veces. Cuando abres los ojos, estás apuntando directamente al primo de Paula, Prudence Pivot. Usted dice: "¡Rápidamente! Aquellos de ustedes que todavía están parados. Si son más bajos que Prudence, vengan aquí. Si son más altos que Prudence, párense allí. Si tienen la misma altura, pueden entra en cualquier grupo ".

Los niños arrastran los pies, y pronto están parados en los dos grupos. Cuenta y encuentra 37 niños en el grupo más bajo y 22 niños en el grupo más alto. Sabes que Paula y otros 59 niños más pequeños están sentados en las gradas. Junto con los 37 niños más pequeños aún en pie, usted sabe que un total de 97 niños son más bajos que Prudence. ¡Por lo tanto, Prudence es el 98 ° niño más bajo!

Quickselect FTW!