Resumen: Esta lección trata de ilustrar uno de los algoritmos de ordenación más utilizados, el quicksort. En función de la edad de los estudiantes se puede introducir el concepto de recursividad.
Breve descripción: La ordenación de información (números, listas alfabéticas, etc.) es una tarea habitual en el procesamiento de datos. Hay muchos algoritmos de ordenación, aquí se va a presentar el funcionamiento del algoritmo quicksort, uno de los más rápidos, especialmente cuando se trabaja con listas muy largas.
El quicksort fue ideado por C. A. R. Hoare, y está basado en la técnica “divide y vencerás”, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
Edad recomendada: A partir de 8 años
Nivel: Básico
Habilidades del siglo XXI: Pensamiento computacional, Creatividad
Objetivo: Esta lección está diseñada para introducir a los niños los algoritmos de ordenación, concretamente el algoritmo quicksort. Además, en función, de la edad y madurez de los niños se puede introducir el concepto de recursión.
Herramientas: Se van a necesitar un conjunto de elementos ordenables (contenedores con medidas y/o pesos diferentes, piezas de puzles con números, cartas, etc.). Para este ejemplo se ha escogido un palo de la baraja española.
Actividad práctica
Se va a ilustrar cómo funciona el algoritmo quicksort.
1. Se van a barajar las cartas.
2. Se va a escoger una de las cartas al azar, ese elemento lo vamos a denominar pivote.
3. Todas las tarjetas se comparan con el valor del pivote, y se crean dos listas, una con los valores más ligeros, que se colocan a la izquierda, y una con los valores más pesado para el pivote, que se colocan a la derecha. Si hay valores iguales a pivote puede ser colocado indiferentemente en cualquiera de las listas.
4. Repita el procedimiento con cada uno de los grupos resultantes. Un pivote se elige y se organiza en dos sublistas.
5. Repita este procedimiento en los grupos que faltan para que ningún grupo tiene más de un objeto en ella.
6. Una vez que todos los grupos se han dividido a los objetos individuales, los objetos estarán en orden del más ligero al más pesado.
