Aprende a ordenar mejor que tu madre

Mucha gente tiende a pensar, dejándose llevar por estereotipos, que un matemático debe ser una persona sumamente ordenada. Y no, créanme, no tiene nada que ver. Sin embargo, sí que las matemáticas se han ocupado de problemas relacionados con ordenar objetos, motivados por muchos problemas prácticos. Especialmente con la aparición de la informática y su necesidad de almacenar y ordenar de forma inteligente y eficiente datos con el fin de mejorar, en tiempo y espacio de disco, el rendimiento de esas aplicaciones que tanto nos han cambiado la vida.

En este sentido, un problema muy complicado, (NP-duro, como aquel del que hablamos hace un tiempo por aquí), es el conocido como 'bin packing' (empaquetamiento en cajas). En el 'bin packing' de lo que se trata es de almacenar una serie de objetos con distintas formas y tamaños, usando el menor número de cajas posibles. Si han hecho alguna mudanza saben de qué les hablo. En otro caso, pueden leer lo que contaba hace poco mi amiga Mati. Pero, creo, que en ambos casos, coincidirán conmigo en que el problema, de entrada, parece bastante complicado.

Sin embargo, hay un problema relacionado con ordenar que parece mucho más simple de resolver y que, no obstante, si no se hace de forma inteligente, nos pueda llevar muchísimo más tiempo del necesario: ordenar exámenes, por ejemplo, alfabéticamente. Sí, imaginen que tienen que ordenar 4.000 exámenes (no sé, de selectividad, por ejemplo) siguiendo el orden alfabético de los estudiantes, ¿cómo lo harían?

Mucha gente te mira raro cuando les formulas la pregunta anterior, algunos hasta con cierta condescendencia, en plan “la pobre...”. Porque, piensan, no hay misterio: solo hay que ir cogiendo un examen cada vez y colocarlo en el sitio que le va correspondiendo en el montón de los que ya están ordenados, mirando desde el principio cuáles van delante de él, alfabéticamente, hasta que encuentres uno que va detrás.

Sí, está bien. Así se puede. Es lo que llamamos cuando hablamos de algoritmos de ordenación, el método de inserción. Si en lugar de con exámenes y por orden alfabético, lo hacemos con números, por simplificar el ejemplo, se trataría de ordenar de menor a mayor un conjunto de números y este método, el de inserción, funcionaría de la siguiente manera. Supongamos que tenemos que ordenar el siguiente conjunto de números, de menor a mayor

{5, 3, 1, 6, 4, 2}.

Siguiendo el método de inserción, comenzaríamos con el 5 y lo comparamos con el siguiente, el 3, como es mayor, lo intercambiamos. A continuación, comparamos el 5 con el siguiente, el 1, como es mayor, lo intercambiamos. Comparamos el 1 con el anterior, el 3, y de nuevo intercambiamos. Ya tenemos ordenado los 3 primeros, comparamos el 5 con el siguiente, 6, no hacemos nada. Vamos a por el 6, lo comparamos con el próximo, 4, intercambio. Nos quedaría {1, 3, 5, 4, 6, 2} y necesitamos hacer otro intercambio para colocar al 4 en su sitio y llegar al {1, 3, 4, 5, 6, 2}. Seguidamente comparamos el 6 con el siguiente, el 2, y hacemos los intercambios necesarios para insertar al 2 en su posición. En la siguiente imagen se van señalando, paso a paso, todos los intercambios.

Muchos pasos, ¿no? Y eso que solo son seis exámenes... Pues sí, es un método bastante lento.

En lenguaje algorítmico, decimos que tiene una complejidad de orden n²; es decir, que si tenemos n datos (exámenes, números...) que ordenar, necesitamos realizar del orden de n² operaciones. O sea, que para 10 números serían del orden de 100, 10.000 para 100 números, y del orden de un millón de operaciones para ordenar 1.000 datos. Mucha tela...

Seguro que a alguien se le ha ocurrido lo siguiente: elegir el más pequeño y ponerlo el primero; de los que quedan, elegir el más pequeño y ponerlo el segundo; de los que quedan, elegir el más pequeño y ponerlo el tercero... Sí, también se puede hacer así, sí. Y también serían necesarias del orden de n² operaciones, como en el de inserción.

¿Cómo lo haría tu madre? Bueno, lo primero que hay que saber es que lo mejor que se puede conseguir es un método que lo resuelva realizando del orden de n x log(n) operaciones (donde log(n) es el logaritmo en base 2 de n). Esto está demostrado, no se puede hacer mejor que eso. Al menos con un ordenador.

Pero este número de operaciones, n x log(n), (y por tanto, el tiempo necesario para realizarlas) es bastante menor que el de n². Por ejemplo, para 10 números, un algoritmo n x log(n)realiza del orden de 10 x log(10)= 10 x 3,321928 operaciones, alrededor de 34 y no 100; para 100, n x log(n)realiza del orden de 100 x log(100)=100 x 6,643856 operaciones, unas 665 (en comparación con las 10.000 del n²); y para 1.000 números, serían 1000 x log(1000) = 1000 x 9,965784, o sea, del orden de 10000, en comparación con el millón de operaciones del n².

Espero que esto nos convenza de usar un método de ordenación de orden n x log(n) antes que un método n².

Uno de los métodos óptimos n x log(n) para ordenar alfabéticamente exámenes, o listas de números de menor a mayor, se basa en aquello tan conocido de divide y vencerás. Se trata de separar los exámenes en distintas pilas de menor tamaño, ordenar cada pila y, por último, peinar las pilas (entremezclarlas convenientemente) y conseguir la ordenación total. Es lo que se conoce en algorítmica como el algoritmo de ordenación por mezcla ('merge sort').

Vamos a ver cómo ordenaría el mismo conjunto:

{5, 3, 1, 6, 4, 2}.

Lo primero es dividir en conjuntos lo más pequeños posible:

{5,3} {1,6} {4,2}

Ordenamos cada uno de estos 3 conjuntos:

{3,5} {1,6} {2,4}

Ahora peinamos los 2 primeros, comparando el primero de cada uno de ellos y eligiendo el menor:

{3,5} {1,6}

1 es menor que 3, se pone el primero;

{3,5} {6} → {1}

comparamos los primeros de cada lista para buscar el segundo, el 3;

{5}{6} → {1,3}

el siguiente será el 5, y, por lo tanto, el último será el 6:

{1,3,5,6}.

Ahora peinamos {1,3,5,6} y {2,4}:

{1,3,5,6} y {2,4} → {1}

{3,5,6} y {2,4} → {1,2}

{3,5,6} y {4} → {1,2,3}

{5,6} y {4} → {1,2,3,4}

Y como solo nos queda una lista, la {5,6}, la ponemos al final

{1,2,3,4,5,6}

Y ya. Tal vez con este ejemplo tan simple no se aprecie la diferencia, pero, créanme, cuando se trata de más de 30 exámenes, este método es mucho más eficiente que el de ir ordenando por inserción.

Este algortimo, el de mezcla o 'merge sort' (en inglés) se lo debemos, nada más y nada menos, que a John von Neumann, una de las mentes más brillantes del siglo pasado que, aún rodeado de otras mentes brillantísimas, conseguió destacar por encima de ellas.

Hay otros métodos de ordenación que necesitan del orden de n x log(n) operaciones, como este de Von Neumann, que se usan en algorítmica, igualmente eficientes. Pero a la hora de ordenar exámenes, este es mi favorito. Les dejo una animación hecha con distintos algoritmos de ordenación en las que se intuye la eficiencia y rapidez de cada uno de ellos.

Pero, como hemos dicho, ninguno mejor que n x log(n). Bueno, mejor que n x log(n) solo lo puede hacer tu madre.