Este fin de semana me toca ordenar mis libros. He sufrido un ultimatum por parte de mi mujer: «o los ordeno o terminan en la biblioteca local como donación anónima».
Sin embargo, como no me apetece empezar tan pronto, he decidido refrescar la memoria con una serie de vídeos que explican diferentes maneras de ordenar una lista de elementos de una forma muy entretenida. Han sido elaborados por el equipo del profesor Z. Kátai de la Sapientia University de Rumanía, como parte del proyecto Algo-Rythmics.
Los «algoritmos de ordenación» son métodos diseñados para recolocar una lista de elementos de menor a mayor siguiendo algún criterio. Todos los hemos utilizado, de forma más o menos consciente, en nuestra vida cotidiana al ordenar, por ejemplo, una baraja de cartas. Incluso estoy seguro que cada uno tiene el suyo propio. Los ordenadores ordenan elementos de forma continua, y aquellos que estudian programación están muy acostumbrados a los diferentes métodos que existen.
Veamos algunos de ellos, los más elementales:
Algoritmo de inserción
Este algoritmo quizás sea uno de los más obvios para una persona. Consiste en ordenar los dos primeros, a continuación se coge el tercer elemento y se le coloca en su posición con los otros dos. Se toma el cuarto y se le coloca en su posición, y así hasta terminar con la lista completa.
Puedes verlo «en danza» en el siguiente vídeo:
El algoritmo es sencillo pero nuestra experiencia nos dice que para ordenar listas grandes acaba siendo demasiado largo ya que obliga a una gran cantidad de comparaciones para los últimos elementos de la lista.
Ordenamiento por selección
Este es otro de los algoritmos más elementales. Consiste en buscar el elemento más pequeño e intercambiarlo por el primero. Tomamos la lista sin el primer elemento y repetimos el proceso, buscamos el más pequeño y lo intercambiamos por el segundo. Repetimos el proceso hasta el final.
Una variante no requiere del intercambio, sino que basta con tomar el pequeño, luego el segundo, etc. Al igual que en el caso anterior, cuando las listas son muy largas, el algoritmo se vuelve poco eficiente al necesitar un montón de comparaciones para encontrar el mínimo en cada paso.
A continuación veremos otros dos algoritmos más eficientes, es decir, que necesitan de un menor número de pasos para completar la ordenación.
El ordenado rápido
El algoritmo de ordenado rápido consiste en lo siguiente:
- Se elige un elemento de la lista (pivote).
- Se recolocan todos los elementos de manera que los menores queden a un lado y los mayores al otro. En este momento el pivote está en su sitio de la lista.
- Se repite el proceso con las dos partes que quedan, la de los elementos más pequeños y la de los más grandes.
Es aconsejable, pero no indispensable, tomar como pivote un elemento lo más centrado posible. Así el algoritmo resulta más eficiente. Este método se llama así porque es el más rápido de todos, eso si, siempre que se acierte la elegir el pivote.
Ordenamiento por mezcla
Fue desarrollado por el matemático John Von Neumann, es una aplicación de la técnica «divide y vencerás» y resulta muy eficiente para listas muy grandes. El algoritmo consiste en separar la lista en grupos más pequeños, ordenarlos cada uno y luego ir mezclando los grupos.
La lista se divide en dos grupos, y cada uno en otros dos, y así de forma recursiva. Cada pequeño grupo se ordena y luego se mezcla con los compañeros. Esta mezcla siempre es más fácil al estar los grupos ordenados porque bastará comparar los primeros elementos de cada grupo y luego colocarlos por orden.
En la web del proyecto Algo-Rythmics se muestra además el funcionamiento de otros dos el «ordenamiento burbuja» y el «ordenamiento shell». También tiene una interesante animación en la que se comprueba la velocidad de cada método. Como es obvio, el que gana es el ordenamiento rápido (el de mezcla no «compite»).
Un momento del test de eficiencia. El ordenamiento rápido ya ha terminado mientras que los otros se afanan en terminar…
También tienen un canal de Youtube: AlgoRythmics con todos los vídeos. También puedes informarte de más algoritmos de ordenación en la Wikipedia, en la entrada Algoritmo de ordenamiento.
Esta entrada aparece en MTHTICS y está bajo una Licencia Creative Commons Atribución-CompartirIgual 3.0 Unported.
MTH TICS 