Novedades

 
 
Picture of Leopoldo Acal
Algoritmos de ordenación con bailes
by Leopoldo Acal - Monday, 4 March 2013, 2:27 PM
 

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.  Esto es un reto para el que lo lea.

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.

La Universidad de Sapientia, de Rumanía, es la responsable de esta idea y de su producción.