Hay muchas cosas que tenemos tan incorporadas, tan automatizadas, que las creemos obvias. Si, en cambio, tuviésemos que explicarle a alguien cómo se suma, nos daríamos cuenta de que sumar no es una habilidad innata. Hay que ir más atrás y contar dos conjuntos de piedritas para saber cuánto suma el conjunto completo. El mismo hecho de contarlas tampoco es innato, hay que aprender la secuencia e ir identificando cada piedrita con un número. Aprender a contar piedritas es el algoritmo más básico que se aprende. A medida que ganamos experiencia con él, lo usamos para sumar piedritas, restar piedritas. Algunos terminan tirando piedritas en el estadio y no avanzan mucho más.
En esta nota, veremos algunos algoritmos bastante más elaborados explicados con danza húngara, rumana y gitana. Eso no se ve todos los días.
Las calculadoras también siguen algoritmos, y actualmente nadie se pregunta qué hace la maquinita si preguntamos por la raíz cúbica de 100. Por dentro, como adivinará el lector, se sigue un algoritmo que converge al resultado. Pasa lo mismo con los lenguajes de programación, que traen esas y muchas otras funciones ya incorporadas y casi nadie se pregunta cómo lo hacen. Sólo buscamos en el índice de funciones a ver si ya existe. ¿Para qué, si alguien ya lo inventó?
Bueno, la verdad es que cada cierto tiempo nacen nuevos lenguajes de programación, o nuevos compiladores para los que ya existen. La gente detrás de esos inventos debe replantearse la manera más eficiente de sumar, transponer, invertir y diagonalizar matrices, maximizar y minimizar y muchas otras tareas. Es como reinventar la matemática de cero para enseñársela al autómata y hacerlo trabajar rápido, con pocos recursos, estabilidad y precisión.
Uno de los algoritmos más estudiados, por la multiplicidad de soluciones y el comportamiento variable en relación a la cantidad de elementos de un conjunto, es el algoritmo de ordenamiento. Algunos son muy rápidos en conjuntos pequeños, pero se vuelven lentísimos conforme aumenta la población. Otros sólo tienen sentido cuando se trata de conjuntos grandes pero son muy aparatosos para ordenar 5 elementos.
En el sitio I, Programmer, publicaron ejemplos de cómo funcionan los algoritmos de ordenamiento usando danzas típicas de Europa del Este para ilustrarlos. Primero el más simple, el Bubble Sort. Se recorre el conjunto intercambiando de posición los elementos que no están en el orden correcto. El algoritmo “acompaña” al último elemento que cambió a una posición más alta, hasta encontrar un elemento mayor para a éste, y así va quedándose con el mayor hasta alcanzar el final del conjunto. Luego empieza de nuevo y, si al terminar el recorrido no hay modificaciones, entonces ha terminado.
Segundo, Shell Sort, es como el anterior pero compara individuos no necesariamente adyacentes.
El Insert Sort opera en principio como el Bubble Sort, pero la secuencia no acompaña al mayor elemento que ha cambiado de posición sino que lo deja en pausa y primero comprueba si el elemento que ha descendido una posición debe seguir descendiendo. Cuando termina esa comprobación vuelve al elemento mayor que había dejado en pausa. El siguiente es un baile rumano, algo más lineal que los húngaros.
Finalmente, el Select Sort toma un elemento que será el protagonista y lo va comparando con el resto del conjunto. Si encuentra un elemento menor, intercambian posiciones y el menor pasa a ser el protagonista. Si un protagonista recorre todo el conjunto sin encontrar ningún número mayor, significa que está en la posición correcta y el protagonismo pasa al siguiente. Este algoritmo no es más caótico que los otros, pero el baile gitano elegido para representarlo si es bien desordenado:
Faltaron los dos algoritmos más eficientes para conjuntos grantes: el Quick Sort, que usa un pivote para subdividir el conjunto y ordenar en paralelo, y el Merge Sort de John Von Neumann, que también divide para hacer subrutinas de ordenamiento en paralelo. Confiamos en que los lectores lo intentarán en su próximo cumpleaños.
Por mientras, los integrantes del instituto Syntax Error de FayerWayer (son los de la sala del fondo) están trabajando para expandir este tipo de demostraciones y así utilizar escenas de la vida cotidiana para acercar a la gente común a la ciencia. Según otras interpretaciones, sería una manera de utilizar la ciencia para acercar la vida cotidiana a los informáticos.
En nuestros próximos proyectos, usaremos el mosh pit de un concierto de Anthrax para representar el movimiento browniano, el juego “a parir la chancha” para ejemplificar la fisión atómica y las teleseries chilenas para mostrar la función str_replace, porque con suerte le cambian nombre a los personajes antes de copiar un libreto.
Link: Sorting algorithms as dances (I, Programmer)
