En ocasiones, y sobre todo por falta de tiempo, apilamos los libros de nuestra biblioteca personal sobre mesas o mismamente en el suelo. Nos decimos que ya el fin de semana los colocaremos en su sitio de la estantería, pero no lo hacemos. Y esto es algo que se repite en el tiempo haciendo que cada vez tengamos más libros sin orden por casa. Ahora bien, y llegado el momento de su colocación, ¿cuál es la forma más rápida de ordenar alfabéticamente todos esos libros?

Existen distintos métodos, pero hay uno realmente rápido y eficaz cuando hablamos de una gran cantidad de libros a ordenar. Gracias a una animación de TED-Ed (What’s the fastest way to alphabetize your bookshelf?), creada por Anton Trofimov a partir de una lección de Chand John, podemos conocer todos estos métodos de manera clara y sencilla. El vídeo está orientado a una biblioteca universitaria, pero sería de utilidad para cualquier biblioteca (incluida nuestra biblioteca personal).

Trabajas en la biblioteca de la universidad. Estás en medio de una tarde tranquila cuando, de repente, llega un envío de 1.280 libros. Los libros están en línea recta, pero todos están fuera de servicio y el sistema de clasificación automática está roto. ¿Cómo puedes ordenar los libros rápidamente? Chand John muestra cómo, arrojando luz sobre cómo los algoritmos ayudan a los bibliotecarios y los motores de búsqueda a clasificar rápidamente la información.

Los métodos (algoritmos) comentados son Bubble Sort, Insertion Sort y QuickSort. Bubble Sort es simple, pero lento. Requiere comparar uno por uno cada uno de los libros hasta que llegan a su lugar. Siguiendo el ejemplo anterior, se tardarían 9,5 días en ordenar los 1.280 libros. Insertion Sort requiere comparar cada libro con la mitad de todos los libros que le preceden, lo que haría que se necesitaran 5 días en colocarlos todos. El último método, QuickSort, es un método de subconjuntos a partir de un elemento tomado al azar. Gracias a él se podrán ordenar todos los libros en 3,3 horas.

3 formas de colocar los libros de tu biblioteca personal, o cualquier biblioteca, en la estantería

Veamos en detalle cada uno de los métodos para entenderlos mejor:

  1. Bubble Sort: Una forma sería comenzar por el primer par de libros en un extremo de la fila y si los dos primeros están en orden, dejarlos como están. De lo contrario, intercambiarlos. Hacer lo mismo con el segundo y el tercero, repetir el procedimiento y seguir hasta llegar al final de la fila. En un momento dado, se encuentra el libro que debe ser el último, se sigue intercambiándolo con los libros posteriores desplazándolo a lo largo de la fila hasta que llegue al final. Volver a empezar desde el principio y repetir el mismo procedimiento para colocar el segundo en el lugar que le corresponde; seguir hasta ordenar todos los libros. Es un método simple, pero lento.
  2. Insertion Sort: Una segunda técnica implica empezar con solo los primeros 2 libros para luego comparar el tercer libro con el que se encuentra en el segundo lugar. Si le corresponde colocarlo delante de este segundo libro, intercambiarlos, luego compararlos con el primero en el primer lugar y volver a intercambiarlos si hace falta. Ya se han ordenado los primeros tres. Seguir con un libro a la vez, ordenándolos por conjuntos, comparando cada uno de ellos e intercambiando con el de delante hasta encontrar el lugar que le corresponde entre los ya ordenados. En promedio, creemos que solo es necesario comparar cada libro con la mitad de todos los libros que le preceden.
  3. QuickSort: Elegir un libro al azar. Usarlo de separador y luego compararlo con todos los otros libros. Luego, dividir la línea y colocar todos los libros de antes de la separación a la izquierda y los otros a la derecha. Acabas de ahorrarte un montón de tiempo y sin tener que comparar todos los libros de la izquierda con todos que tiene a la derecha. Ahora, al fijarte solo en los de la izquierda vuelve a elegir uno al azar y separa los libros de delante y detrás de ese en dos grupos. Sigue dividiendo los libros en base al mismo principio hasta que llegues a tener pequeñas pilas de libros, listas para ordenarlas en base al método de inserción.

Sin duda que el método QuickSort es mucho más rápido que los otros dos, y puede hacer que ahorremos un tiempo valiosísimo obteniendo el mismo resultado en nuestra biblioteca personal o cualquier otro tipo de biblioteca. Este algoritmo de clasificación, que sirve como método sistemático para colocar elementos en orden, fue desarrollado por el informático británico Tony Hoare en 1959.

Quicksort es un algoritmo de divide y vencerás. Quicksort primero divide un conjunto grande en dos subconjuntos más pequeños: los elementos bajos y los elementos altos.