Quicksort explicado a los niños

16

El año pasado, estaba leyendo un fantástico artículo sobre "Mecánica cuántica para jardines de infancia" . No fue papel fácil.

Ahora, me pregunto cómo explicar quicksort en las palabras más simples posibles. ¿Cómo puedo probar (o al menos handwave) que la complejidad promedio es y cuáles son los mejores y los peores casos para una clase de jardín de infantes? O al menos en la escuela primaria?O(norteIniciar sesión⁡norte)

algorithms education algorithm-analysis didactics sorting jonaprieto
fuente
99
¿Quieres demostrar la complejidad del quicksort ... a un grupo de niños de tres años ...? Buena suerte.
2
Intenta usar su lenguaje, el problema es que es muy limitado y biológicamente no están preparados para esta complejidad. Los siguientes pasos, como en un algoritmo, no se desarrollan completamente hasta que tienen seis o siete años. Estás enfrentando un desafío biológico.
44
En realidad, no lo sugeriría para Kindergarten, pero buscar en youtube para la clasificación rápida (y otros algoritmos de clasificación) proporcionan muchas buenas representaciones. Personalmente prefiero los bailes folclóricos de Hugarian. Ver youtube.com/watch?v=ywWBy6J5gz8 .
2
El artículo del que habla tiene un título pegadizo pero un contenido muy complejo como Hilbert Space Model, entonces, ¿qué busca realmente?
2
Me daría por vencido en intentar explicar completamente la clasificación rápida, y en su lugar trataré de darles a los niños una comprensión de "divide y vencerás". Incluso si no tienen la edad suficiente para asimilar completamente la recursión, la idea de dividir un gran problema en problemas más pequeños sería realmente valiosa. Personalmente, tomaría una sólida comprensión fundamental de dividir y conquistar cualquier día sobre una noción incompleta de algoritmos complejos.
Vincent Gable el

Respuestas:

14

En esencia, Quicksort es esto:

  1. Toma el primer artículo.
  2. Mueve todo menos que ese primer elemento a la izquierda, todo más grande a la derecha (asumiendo un orden ascendente).
  3. Recurrir en cada lado.

Creo que cada niño de 4 años en el planeta podría hacer 1 y 2. La recursión podría requerir un poco más de explicación, pero no debería ser tan difícil para ellos.

  1. Repita en el lado izquierdo, ignorando el derecho por ahora (pero recuerde dónde estaba el medio)
  2. Sigue repitiendo con los lados izquierdos hasta llegar a nada. Ahora vuelve al último lado derecho que ignoraste y repite el proceso allí.
  3. Una vez que te quedas sin los lados derecho e izquierdo, listo.

En cuanto a la complejidad, el peor de los casos debería ser bastante fácil. Solo considere una matriz ya ordenada:

1 2 3 4
  2 3 4
    3 4
      4

Bastante fácil de ver (y demostrar) que es .12norte2

No estoy familiarizado con la prueba de caso promedio, por lo que realmente no puedo hacer una sugerencia para eso. Se podría decir que en un conjunto no ordenado de longitud la probabilidad de elegir el elemento más pequeño o más grande es 2l , entonces ...?2norte

Kevin
fuente
Tal vez (d & c) la recursividad es mejor y se explica de forma más natural con el paralelismo inherente.
Raphael
2
Estoy de acuerdo Mi instinto fue utilizar una metáfora de dar las dos pilas a tus amigos para trabajar.
Christian Mann
3
Afirmo que los niños de cuatro años son (con posibles excepciones) fundamentalmente incapaces de comprender la recurrencia, no importa cuánto lo intenten. El cerebro simplemente no es lo suficientemente maduro. Hay fases bien definidas en el desarrollo del cerebro, por ejemplo, el punto donde los niños se vuelven conscientes de sí mismos, donde se dan cuenta de las consecuencias futuras de las acciones actuales, y donde primero entienden el sarcasmo que sigue un cronograma estrictamente controlado que no se puede reordenar deliberadamente y está altamente conservado entre los niños. Creo que entender la recursividad cae en la misma categoría.
Konrad Rudolph el
16

Quicksort es bastante fácil de entender si entienden el conteo básico y la división por 2. Haga un montón de tarjetas X, numerelas de 1 a X y revuélvalas. Entonces aquí está la explicación:

OK, tenemos este mazo de (digamos 20) cartas aquí. Queremos ponerlos en orden, entonces 1 es primero, luego 2, luego 3, y así sucesivamente. Aquí hay una forma muy rápida de hacerlo.

Primero, veamos este mazo y hagamos dos pilas de él. La mitad de 20 es 10, por lo que cualquier cosa mayor que 10 va en este montón a la derecha, y cualquier cosa más pequeña va en este montón a la izquierda. (Asegúrese de demostrar sobre la marcha).

Ahora, hagamos lo mismo con las pilas más pequeñas. ¿Qué es la mitad de 10? (Alguien dice "cinco") ¡Eso es correcto! Entonces, cualquier cosa mayor que 5 va en esta pila a la derecha, y cualquier cosa más pequeña va en esta pila a la izquierda.

Y por aquí, tenemos el grupo que es más grande que 10. ¿Entonces la mitad de 10 es 5, y qué es 10 más 5? (Alguien dice "quince") ¡Eso es correcto! Entonces, cualquier cosa mayor que 15 va en esta pila a la derecha, y cualquier cosa menor que 15 va en esta pila a la izquierda.

Y ahora las pilas se están volviendo lo suficientemente pequeñas como para que puedas mirarlas fácilmente y ponerlas en orden. Mira, aquí tenemos 2, 4, 5, 3, 1. Entonces los cambiamos así, y puedes ver 1, 2, 3, 4, 5. Así que hagamos lo mismo con las otras pilas, y luego las ponemos en orden y ¡mira! ¡Están en orden del 1 al 20!

Felicidades. ¡Acaba de enseñar a un grupo de niños los principios básicos de un algoritmo adaptativo de clasificación rápida! Puede ir un poco más profundo que eso dependiendo de la madurez mental, pero ir mucho más allá de este punto requiere cierta comprensión de la lógica formal.

En cuanto a demostrar su complejidad, eso es más complicado. Es una de las cosas que requiere lógica formal, y tendrán que entender los principios básicos de la notación big-O en primer lugar. Es posible que desee retrasar esa parte al principio.

Mason Wheeler
fuente
No creo que su ejemplo no sea bueno porque esencialmente ordena las claves, no los valores, y solo puede saber qué está en la posición 15 al haber ordenado ya.
Thorbjørn Ravn Andersen
@ Thorbjørn: ¿Quién dijo algo sobre pares clave / valor? Este es un tipo entero simple para explicar el concepto básico.
Mason Wheeler
Pensarlo en el algoritmo que describe no es un ordenamiento rápido, ya que no utiliza un elemento pivote.
Thorbjørn Ravn Andersen
1
@ ThorbjørnRavnAndersen: Por supuesto que sí; es solo que él sabe qué elementos hay para poder elegir la mediana.
Raphael
@Raphael y su distribución. Las tarjetas pueden tener cualquier valor y color y solo tienen una pegatina con su número entre 1 y 20. De ahí mi referencia a la clave / índice y no al valor.
Thorbjørn Ravn Andersen
2

¿Qué tal esto?

Ciencias de la computación desconectadas - Algoritmos de clasificación

No cubre todas sus preguntas, pero es un buen comienzo.

Más recursos sobre este tema están vinculados aquí .

También pusieron a disposición un video que explica los algoritmos de clasificación (incluido el ordenamiento rápido) aquí . Este video realmente ayuda a comprender la diferencia entre los diferentes algoritmos de clasificación para niños pequeños.

TimB
fuente
increíble ! Muy fácil de entender.
Mayur Patil
1

Vea la belleza gráfica de esta pequeña demostración .

ordenación rápida.

gbjbaanb
fuente
1
Creo que eso podría ser demasiado abstracto para los niños.
Raphael
3
No para avergonzarme a mí mismo, pero no entendí ese gráfico hasta que finalmente me explicaron la clasificación rápida en clase.
Christian Mann
Tenga un +1 porque esto es lo que primero se me ocurrió cuando leí la pregunta, pero luego soy un aprendiz visual.
Joshua Drake
3
Esta es realmente una forma incorrecta de explicar cómo funciona quicksort . Si ya conoce el ordenamiento rápido, puede confirmar que esta animación trata sobre el ordenamiento rápido. Si no conoce el ordenamiento rápido, no dice nada excepto que el ordenamiento rápido es un algoritmo de clasificación bastante rápido que utiliza algo de magia. Dependiendo de quién sea la audiencia, puede motivar a la audiencia para que aprenda sobre la clasificación rápida mostrando esta animación, pero no explica nada importante sobre cómo funciona.
Tsuyoshi Ito
La animación es bastante agradable, pero hasta ahora es comprensible para un principiante, incluso para un estudiante universitario a la primera oportunidad.
jonaprieto