Matemáticas para ordenar, por Clara Grima

• Todo lo que las matemáticas pueden hacer hacer por ti a la hora de ordenar y clasificar, por Clara Grima
• Una matemática viene a verte: Todos los miércoles, en La 2 a las 19:45 horas | Disponible en RTVE Play

Clara Grima, presentadora de Una Matemática viene a verte

Soy matemática. Y me gusta. Lo sé, puede que alguien no le encuentre la gracia a este hecho y se imagine que quien teclea estas líneas es un ‘bicho’ raro, asocial, con una mente privilegiada para hacer cálculos mentales mientras sus ojos giran a gran velocidad activando las neuronas que ponen en marcha los algoritmos algebraicos. O que por ser matemática soy una persona extremadamente ordenada. Pues no, no soy nada de eso. Soy muy mala con el cálculo mental y mucho peor con el orden.

Matemáticas y orden

Aunque sí es cierto que la inquietud humana por ordenar ha recibido mucha atención de las matemáticas a lo largo de la historia. 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.

Y es de eso de lo que les vengo a hablar en esta calurosa mañana de mayo, de las matemáticas que nos ayudan a ordenar bien y rápido. Bueno, solo un poco, porque, como he dicho unas líneas más arriba, hay muchísimas matemáticas para el orden.

Además de matemática, soy profesora en la universidad. Entre otras muchas tareas, una de la que me tengo que ocupar periódicamente es la de ordenar alfabéticamente los exámenes de mis estudiantes. Y sí, es una tarea tediosa pero que no puedo evitar.

¿Cómo lo hacen ustedes? ¿Cómo ordenan alfabéticamente una pila de exámenes? Mucha gente me mira raro cuando les formulo la pregunta anterior, algunos hasta con cierta condescendencia, pensando “la pobre...” Porque, piensan, que 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. 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}

Método de inserción

Métodos de inserción

Una matemática viene a verte, métodos de inserción RTVE

Siguiendo el método de inserción, comenzamos 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 ordenados 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.

Complejidad de orden n²

En lenguaje algorítmico, decimos que este algoritmo, el algoritmo de inserción, 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 operaciones, 10.000 para 100 números, y del orden de un millón de operaciones para ordenar 1.000 datos.

Alguien podría pensar en mejorar el método anterior de la siguiente manera: 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.

¿Se puede hacer más rápido?

Uno de los métodos óptimos 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}, comparando siempre los primeros de cada lista:

{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}

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. Porque, como hemos dicho, el método de inserción realiza del orden de n² operaciones para ordenar n exámenes y este, el merge sort, solo realiza n x log(n). Y este número de operaciones es mucho menor. Huy, lo que he dicho. Voy a tratar de convencerles con algunos ejemplos.

• Para 10 números, el merge sort realiza del orden de 10 x log(10)= 10 x 3,321928 operaciones, alrededor de 34 y no 100; el de inserción, como dijimos antes, realiza 102= 100.
• Para 100, merge sort realiza del orden de 100 x log(100)=100 x 6,643856 operaciones, unas 665, en comparación con las 1002=10.000 del método de inserció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 (10002 ) del método de inserción.

¿Le he convencido de que es mejor dividir los exámenes en montoncitos y peinarlos? Lo dejamos por aquí pero hay muchas más matemáticas que nos ayudan a ordenar, clasificar y empaquetar. Hablamos de ellas en el programa 'Comer, beber y... matemáticas', con la cocinera Pepa Muñoz y el catedrático, Emilio Carrizosa.

Nos vemos en La 2.

* Puedes disfrutar del programa Una matemática viene a verte cada miércoles a las 19:45 horas en La 2 y siempre, cuando quieras -gratis y online- en RTVE Play.