Algoritmos para optimizar tu vida: Ordenamiento

Estamos tan inmersos en listas ordenadas que, como el aire, no notamos su presencia y cuando lo hacemos, resulta que están en todos lados: nuestro email muestra el top 50 de los miles de correos que recibimos; Uber Eats enseña los restaurantes más cercanos o mejor valorados; Google, más que un motor de búsqueda, es un motor de ordenamiento que filtra nuestro texto de entre cientos de millones de páginas web y muestra las diez más relevantes.

Si buscamos el más grande, el más pequeño, el más barato, el más caro o simplemente buscamos algo, hay un algoritmo de ordenamiento detrás y ¡atención, diseñadores!, el orden es la clave de la experiencia humana en la información. Es más, no solo ordenamos información y objetos, ¡también lo hacemos con personas!

El ordenamiento es la quintaesencia de la computación y, por si fuera poco, también llevó a su creación.

El delirio de ordenar

Todo comenzó en la segunda mitad del siglo XIX, cuando la población de los Estados Unidos crecía en promedio un 30% cada década y con ello la oficina encargada del censo pasó de un puñado de empleados a contratar cientos, logrando apenas terminar el censo de 1880 justo antes de que el de 1890 comenzara. ¿Cuánto tardaría entonces el siguiente padrón? ¡Era una locura!

Fue entonces cuando el inventor Herman Hollerith, inspirado por las tarjetas perforadas del tren de la época, diseñó un sistema de tarjetas de manila perforadas para guardar información y una máquina – la máquina de Hollerith – para contar y ordenarlas.

Máquina de Hollerith

Se le fue otorgada la patente y el gobierno adoptó la máquina para el censo de 1890, dejando a la gente atónita por su velocidad y precisión. Algunas personas pensaban que su utilidad era limitada y únicamente el gobierno la usaría, pero estaban equivocadas. La compañía se fusionó con otras del ramo y se convirtió en Computing-Tabulating-Recording Company, para luego renombrarse como International Business Machines, o IBM como lo conocemos hoy día.

El tamaño sí importa

Tradicionalmente, solemos pensar que resulta más eficiente realizar las cosas al por mayor – como comprar. Sin embargo, en el giro del ordenamiento no es del todo cierto: Si quisiéramos ordenar un librero con cien libros, nos tomará más tiempo que ordenar dos libreros de cincuenta libros cada uno; tenemos el doble de cosas por organizar y el doble de espacios en donde podrían ir.

De lo anterior podemos inferir que una forma de evitar más trabajo al ordenar es minimizar el número de cosas a arreglar. Mientras que este pequeño tip puede funcionar en nuestros estantes de libros, no lo hace tan bien en las computadoras: a cada minuto, millones de datos son ordenados y la cifra sigue creciendo. Tal vez sería conveniente elegir una mejor forma de hacerlo y para ello, la mediremos.

El peor caso

Seguramente has oído de los cubos Rubik y conoces a alguien que ha tratado de armarlos, incluido tú mismo. El truco consiste en juntar las piezas del mismo color en una sola cara para cada uno de los seis colores del cubo.

El récord mundial de resolución para un cubo de 3x3x3 lo ostenta el chino Yusheng Du con el sorprendente tiempo de 03.47 segundos. Definitivamente es una cifra difícil de batir, pero hay una certeza del 100% de que cualquiera de nosotros puede romper su récord, incluso sin práctica, y tener una marca inmejorable.

Si una máquina nos da un cubo de Rubik con una configuración aleatoria para que nosotros lo resolvamos, eventualmente llegará la combinación donde por puras probabilidades el cubo nos será entregado resuelto, registrando la marca de 0.00 segundos en el libro de Récords Guinness.

Solo hay un pequeño inconveniente: el cubo tiene 43,252,003,274,489,856,000 combinaciones distintas (más de cuarenta y tres trillones) y si cada segundo recibiéramos una configuración diferente de la máquina, sin repetirlas, pudiéramos tardar hasta 1,371,512,026,716 años (1.37 billones de años) – cerca de cien veces la edad conocida del Universo – para tenerlo resuelto al instante. ¡Tal vez sea mejor practicar en todo ese tiempo!

Con esto vemos un indicio de la diferencia entre los computólogos y el jurado de Guinness World Records; mientras los últimos se preocupan por el mejor caso, los primeros están más interesados en el peor de ellos.

Esto se comprende ya que, guiándonos por los resultados de la peor situación, podemos garantizar que un proceso terminará en el tiempo adecuado, respetando así nuestra agenda.

Notación Big-O

La notación Big-O o notación O grande – en referencia a omicrón, letra griega – es la forma con que se miden los algoritmos en los escenarios que involucran el peor caso, tomando como métrica los recursos consumidos según la entrada. En nuestro caso será el tiempo.

Si contamos con nociones de funciones matemáticas resultará más fácil de entender, pero descuida, será lo más sencillo posible y si no acaba por hacer sentido, lo hará al final de la sección.

Para ilustrarlo, imaginemos que organizamos una fiesta con n invitados, donde n puede representar cualquier número. Como preludio a la celebración, limpiaremos la casa y esta actividad consumirá un tiempo que es totalmente independiente del número de invitados.

Este es la más sencilla de las situaciones y se notará como O(1), o tiempo constante. De hecho, para la notación Big-O el tiempo de limpieza es totalmente indiferente, dado que no depende para nada de la lista de invitados. La casa se limpiará en el mismo tiempo así sean uno, mil o n visitantes.

Ahora bien, el tiempo requerido para servir la comida alrededor de la mesa será O(n), o tiempo lineal. Si hay el doble de comensales, se ocupará el doble del tiempo. A la notación Big-O le importa poco si se sirven dos platos o si los huéspedes dobletean. En ambos casos el tiempo consumido responde linealmente al número de personas.

Otra particularidad de la notación es que, si graficamos ambas funciones, los factores lineales sepultan a los factores constantes, haciéndolos irrelevantes. Esto es lo mismo que decir: servir la mesa, o remodelar la casa para la fiesta y luego servir la mesa, son equivalentes para el análisis.

Podrá sonar raro que sea así, pero las computadoras están acostumbradas a procesar valores de n que podrían representar una fiesta con miles de millones de invitados, haciendo que el tiempo para remodelar la casa y limpiarla resulte insignificante comparado con el tiempo para atender la mesa.

¿Qué tal si ahora, al llegar, cada uno de los invitados saluda a los que ya se encuentran? El primero te abrazará; el segundo dará dos apretones de manos; el tercero tres y así sucesivamente; entonces n invitados saludaran a n invitados. Esto se marcaría con O(n^2), o tiempo cuadrático.

Justo como en la comparación anterior, el crecimiento cuadrático enterrará al crecimiento lineal, dejando la complejidad de la fiesta solo con O(n^2). Intuitivamente, la función que describe un crecimiento más rápido – parezca más una línea vertical –  se coronará como la ganadora.

Por si no fuera suficiente, supongamos que cada invitado dobla nuestro trabajo, dándonos O(2^n) o incluso peor, que nos cargue de un trabajo con crecimiento factorial O(n!), del cual los computólogos no hablan más que para hacer bromas o desearían que así lo fuera.

Precisamente una de esas funciones factoriales es la que describe el comportamiento para tener las combinaciones del cubo Rubik. Son muchísimas, ¿no?

Algoritmos de ordenamiento

Dado que todo el tiempo nos encontramos ordenando información, más vale que sea de manera eficiente. ¿Imaginas si Google tardara días en devolver el resultado de la búsqueda?

Con la pequeña introducción a Big-O se nos facilitará la comparación entre los muchos algoritmos existentes, tomando como métrica el tiempo requerido y comenzando con los primeros que son aceptables en términos de eficiencia, los O(n^2).

Nuestro objetivo: ordenar un estante con libros de manera alfabética descendente (A-Z).

Algoritmos cuadráticos

Como primera idea, podemos leer título por título buscando pares de libros fuera de orden – Poe y Ness – invertimos su orden – primero Ness y luego Poe – para luego continuar nuestra búsqueda de pares, volviendo al inicio del librero en cada iteración hasta que no encontremos ningún libro fuera de orden.

Ordenamiento burbuja

Este comportamiento recibe el nombre de ordenamiento burbuja (Bubble Sort). Contamos con n libros fuera de orden y en cada iteración movemos el libro una posición a lo mucho, teniendo en el peor caso – estante ordenado al revés – que mover el primer libro n posiciones hasta el final, lo que resulta después en mover n libros n posiciones u O(n^2).

Otra aproximación, tal vez más natural, sea sacar todos los libros del mueble y regresarlos de uno en uno. Empezaremos por poner el primer texto justo a la mitad del entrepaño, entonces tomamos un segundo libro y lo colocamos a la izquierda o derecha según corresponda. Con el tercer libro, recorreremos los títulos de izquierda a derecha hasta hallar el lugar donde insertarlo. Repitiendo este proceso con los libros restantes, terminaremos con un librero ordenado.

Ordenamiento por inserción

No es de sorprender que este algoritmo sea conocido como ordenamiento por inserción (Insertion Sort) y aunque este ordenamiento es un poco más rápido que el burbuja, no deja de tener una complejidad cuadrática: ordenar un estante con libros no será cinco veces más complejo que ordenar cinco, ¡si no veinticinco veces más!

Divide y vencerás

Quizás nos preguntemos si existe una manera más rápida de ordenar, pero debemos replantear nuestra estrategia con las preguntas adecuadas, tal como ¿cuál es el mínimo esfuerzo requerido para ordenar?

Recordando nuestra mini intro de Big-O, intentaremos ordenar con el más simple de los casos: ¿Es posible ordenar nuestros libros en tiempo constante O(1)? Apenas acabamos de comprobar que no; se requiere comparar al menos n de ellos, poniendo la idea fuera de lugar.

Es difícil imaginar ordenar los libros en tiempo lineal O(n) – así como los vamos pasando al librero, queden acomodados, no importando los demás. Si seguimos buscando soluciones, naturalmente llegaremos al mismo caso cuadrático que acabamos de abordar, debido a que debemos comparar n libros contra n libros.

Hasta ahora sabemos que podemos ordenar tan eficientemente como un algoritmo cuadrático, pero no tanto como un algoritmo lineal. Es aquí donde el aforismo de Julio César y Napoleón hace su aparición (Dīvide et īmpera).

Compiladora de IBM

Como se mencionó anteriormente, IBM creó máquinas para ordenar tarjetas perforadas. Años después, empezaron a producir unas máquinas llamadas compiladoras, las cuales mezclaban dos pilas de tarjetas ordenadas en una sola. Como ambas contaban con un orden, el proceso de unirlas en una sola tomaba un tiempo lineal: era simple como comparar los topes de cada pila, pasar el menor a una nueva pila y repetir hasta que se terminaran.

Sucedió en 1945, cuando John Von Neumann escribió un programa almacenado basado en el funcionamiento de los compiladores de IBM. Ordenar dos tarjetas es tan simple como poner la de menor valor arriba, y si tenemos dos pilas ordenadas de dos tarjetas cada una, podemos apilarlas en un montón de cuatro tarjetas ordenadas. De repetir la estrategia unas pocas veces podemos armar pilas cada vez mayores, todas ordenadas, para finalmente mezclar los resultados y obtener un solo conjunto con cada miembro en su lugar.

Ordenamiento por mezcla

El legendario algoritmo recibe el nombre de ordenamiento por mezcla (Merge Sort) y su poder reside en el hecho de que su complejidad vive entre los tiempos linear y cuadrático, específicamente linearítmico O(n log(n)).

En cada repetición del algoritmo se dobla el tamaño de la pila de libros, así que para ordenar n libros se requieren tantas repeticiones como el número de veces que hay que multiplicar 2 consigo mismo para ser igual o mayor a n; el logaritmo de base 2 de n, dicho de otra forma.

No suena tan sorprendente decir que hemos roto la barrera cuadrática, pero si comparamos las treinta y una repeticiones contra mil millones podremos notar su impacto en las ciencias computacionales.

¿Comparar todo?

Ya se ha probado que la complejidad linearítmica ofrecida a través del ordenamiento por mezcla es lo máximo que podemos aspirar en términos de orden con el fin de organizar completamente un conjunto de n elementos mediante comparaciones sucesivas.

Sin embargo, hay escenarios en donde esto no es definitivo dado que a veces no es necesario tener un conjunto completamente ordenado, evitando la comparación de todos contra todos. Este es el caso del ordenamiento por cubetas o casilleros (Bucket Sort).

Ordenamiento por cubetas

En este, los elementos se agruparán dentro de un número de categorías ordenadas entre sí (cubetas) sin lugar a que un elemento se encuentre en más de una cubeta. Luego podemos usar el ordenamiento por inserción, o cualquier otro algoritmo, para organizar los elementos de cada cubeta. Elegir las m cubetas correctamente nos abrirá a la posibilidad de organizar los elementos en tiempo O(mn), pero como el número de cubetas se vuelve despreciable a medida que n crece, podemos decir que la complejidad es O(n).

Para ejemplificarlo mejor, si para organizar nuestro librero hacemos cubetas por cada letra del alfabeto e ingresamos los libros uno a uno en cada una de ellas mediante su título, ordenarlos internamente se volverá mucho más sencillo. El problema sería elegir cubetas poco útiles (una de A-Z), dejándonos justo donde comenzamos.

¿Punto final?

Apenas conocemos algunos algoritmos de ordenamiento, empero hay otros tan buenos o mejores que mergesort como heapsort o quicksort. No obstante, la pregunta fundamental de todo el tema del ordenamiento es por qué deberíamos ordenar en primer lugar.

Mientras tanto, sabemos que la próxima vez que deseemos ordenar nuestro librero, podemos elegir muchas cubetas o llamar unos amigos para que cada uno ordene un múltiplo-de-2 libros y mezclarlos en el estante. ¡No olviden preparar bocadillos!