Hay líneas de código en tu frigorífico inteligente, en tu televisor, en el termostato de tu casa y, sí, también en un test de embarazo que puede correr Doom. El mundo moderno se sostiene sobre software, y aunque la mayoría de personas usan aplicaciones a diario, muy pocas tienen una idea clara de cómo funciona el código por dentro.
Uno de los problemas más básicos y más interesantes de la programación es tan cotidiano que pasa desapercibido: ordenar cosas. Cuando en Amazon haces clic en «ordenar por precio» o cuando en Spotify ordenas tu biblioteca por artista, hay un algoritmo ejecutándose en milisegundos para resolver ese problema. Y la historia de cómo se resuelve ese problema dice mucho sobre cómo piensan los programadores.
La escena mental: cajas, números y un brazo robótico
Para entender cómo funcionan los algoritmos de ordenación, es útil visualizar el problema de forma concreta. Imagina una fila de cajas colocadas en línea, cada una con un número escrito. Tu tarea es ordenarlas de menor a mayor. Para hacerlo tienes un brazo mecánico con dos capacidades:
- Mover cajas: puede intercambiar dos cajas de posición o insertar una caja en un lugar específico.
- Leer números: tiene una cámara que lee el número de cualquier caja y puede comparar dos cajas para saber cuál tiene el número mayor.
Usando solo estas dos operaciones, ¿cómo ordenarías la fila de forma sistemática y automática? Eso es exactamente lo que hace un algoritmo de ordenación. El brazo mecánico es el procesador, y la fila de cajas es una lista de datos en memoria.
Insertion Sort: ordenación por inserción
El primer enfoque intuitivo es el Insertion Sort o ordenación por inserción. Funciona así:
- Empieza por la segunda caja (la primera no tiene nada con qué compararse).
- Compara esa caja con la anterior. Si la anterior es más grande, inserta la caja delante de ella.
- Pasa a la tercera caja. Compárala con la segunda, luego con la primera si hace falta, hasta encontrar su posición correcta e insertarla ahí.
- Repite este proceso para cada caja hasta llegar al final de la fila.
El algoritmo va caja por caja y coloca cada una en su posición correcta respecto a todas las anteriores, deteniéndose en cuanto encuentra una más pequeña.
La complejidad temporal: cómo se mide si un algoritmo es rápido
Para juzgar si un algoritmo es bueno o malo, los programadores usan una herramienta llamada complejidad temporal, representada con la notación Big O (también conocida como O grande). No mide cuánto tarda en segundos sino cómo crece el tiempo de ejecución a medida que crece la cantidad de datos.
Los casos de ejemplo
- Big O(1): tiempo constante. El algoritmo tarda siempre lo mismo independientemente de cuántas cajas haya. Ejemplo: un algoritmo que solo necesita leer la segunda caja de la fila, sin importar cuántas haya en total.
- Big O(n): tiempo lineal. El tiempo crece proporcionalmente al número de elementos. Ejemplo: contar todas las cajas de la fila, una por una.
- Big O(n²): tiempo cuadrático. El tiempo crece de forma proporcional al cuadrado del número de elementos. Si con 10 cajas tardas 10 segundos, con 50 cajas tardarás 2.500 segundos.
¿Cómo se comporta el Insertion Sort?
- Mejor caso: la lista ya está ordenada. El algoritmo solo compara cada caja con la anterior y no mueve nada. Complejidad: O(n).
- Peor caso: la lista está en orden completamente invertido. Cada caja tiene que compararse con todas las anteriores y moverse al inicio. Complejidad: O(n²).
- Caso promedio: lista aleatoria. Estadísticamente se acerca más al O(n²) que al O(n). El algoritmo tiende a ser lento con muchos elementos.
Bubble Sort: ordenamiento de burbuja
El Bubble Sort o ordenamiento de burbuja es otro enfoque clásico, algo más simple en su lógica:
- Compara la primera caja con la segunda. Si la primera es más grande, intercámbialas.
- Compara la segunda con la tercera, luego la tercera con la cuarta, y así hasta el final de la fila.
- Al terminar la primera pasada, el número más grande habrá «burbujeado» hasta el final. Pero la fila no está ordenada todavía.
- Repite el proceso desde el principio. Tantas veces como sea necesario hasta que no haya ningún intercambio pendiente.
En cuanto a complejidad temporal, el Bubble Sort es muy similar al Insertion Sort: O(n) en el mejor caso y O(n²) en el peor. El Insertion Sort es generalmente algo más rápido, por lo que el Bubble Sort apenas se usa en la práctica. Su única ventaja es que requiere muy pocas instrucciones de código, lo que puede tener valor en dispositivos con memoria extremadamente limitada. Hoy en día se estudia en las carreras de informática principalmente como ejercicio teórico.
Quicksort: el algoritmo de Tony Hoare
En los años 60, un matemático británico llamado Tony Hoare estaba haciendo su posgrado en Moscú investigando traducción automática de lenguaje natural. Necesitaba ordenar palabras de forma eficiente y los algoritmos disponibles no eran suficientemente rápidos para los ordenadores de la época. Así inventó el Quicksort.
El Quicksort sigue una estrategia llamada divide y vencerás (divide et impera en latín, la misma filosofía que usaba el Imperio Romano):
- Elige una caja de la fila como pivote.
- Mueve todas las cajas con un número menor que el pivote a la izquierda, y todas las mayores a la derecha. El pivote queda en el medio.
- Ahora tienes dos subfilas: una a la izquierda (menores) y otra a la derecha (mayores).
- Repite el mismo proceso dentro de cada subfila: elige un nuevo pivote, divide en dos, y así sucesivamente.
- Cuando las subfilas son demasiado pequeñas para dividir, únelas en orden y tendrás la fila completa ordenada.
El resultado es un algoritmo que divide el problema en problemas más pequeños, resolviendo cada uno por separado. La complejidad temporal en el caso promedio es O(n log n), mucho mejor que el O(n²) del Insertion Sort y el Bubble Sort en situaciones reales.
En el peor caso (una lista ya ordenada con un pivote mal elegido), puede degradarse a O(n²), pero en la práctica esto es poco frecuente.
Timsort: el algoritmo que usa Python hoy
El algoritmo de ordenación más sofisticado de los que se usan en producción actualmente es el Timsort, diseñado por Tim Peters específicamente para Python (sí, los programadores a veces le ponen su nombre a sus creaciones). Hoy se usa también en Java, JavaScript y muchos otros lenguajes.
Lo que hace al Timsort especial es que no usa una sola estrategia, sino que adapta su enfoque según las características de los datos:
Paso 1: decidir la estrategia
Si la lista tiene menos de 64 elementos, el Timsort simplemente aplica Insertion Sort. Para listas pequeñas, la simplicidad del Insertion Sort lo hace suficientemente rápido y no vale la pena usar algo más complejo.
Paso 2: identificar carreras (runs)
Para listas más grandes, el Timsort busca runs: segmentos de la lista que ya están ordenados (de forma ascendente o descendente). Cuando detecta un cambio de tendencia (de subida a bajada o viceversa), corta ahí. Si un segmento está en orden descendente, simplemente lo invierte. Al final de este paso, la lista está dividida en múltiples subsecciones, cada una ordenada internamente.
Paso 3: unir las carreras con Merge Sort
El Timsort usa la técnica del Merge Sort para unir las subsecciones ordenadas en una sola lista final. El proceso de fusión compara el primer elemento de cada subfila y coloca el menor en la lista resultado, repitiendo hasta que todas las subfilas quedan vacías y la lista final está perfectamente ordenada.
La complejidad temporal del Timsort:
- Mejor caso: O(n). Si la lista ya está ordenada, el algoritmo lo detecta y termina rápido.
- Caso promedio: O(n log n). Igual que Quicksort.
- Peor caso: O(n log n). Aquí está la gran ventaja sobre Quicksort, que en el peor caso llega a O(n²).
El Timsort es, en términos de complejidad temporal, el mejor de todos los que hemos visto.
Una nota sobre los algoritmos más curiosos
El mundo de los algoritmos de ordenación tiene también sus notas de humor. Existen algunos que merecen mención especial no por su eficiencia sino por su historia:
- I Can’t Believe It Can Sort: literalmente «no me puedo creer que esto ordene». Es un paper académico donde alguien publicó un algoritmo funcionalmente parecido al Insertion Sort pero con una variante tan extraña que el propio autor no podía creer que funcionara. Su única ventaja real es que tiene cuatro líneas de código.
- Slow Sort: un algoritmo diseñado intencionadamente para ser lo más lento posible. Usa la estrategia opuesta al divide y vencerás: «multiplica y ríndete». Funciona, pero es terriblemente ineficiente. Alguien dedicó tiempo real a programar el peor algoritmo posible que aun así ordene correctamente.
Por qué importa todo esto
En la práctica, la mayoría de los programadores no necesitan implementar algoritmos de ordenación desde cero. En Python, el comando sort() llama automáticamente al Timsort. En JavaScript, los motores modernos usan variantes optimizadas. La librería ya está ahí.
Pero entender cómo funcionan estos algoritmos tiene valor real. Cuando se habla de optimización de software o de optimización de videojuegos, lo que está ocurriendo por detrás muchas veces es exactamente esto: elegir el algoritmo correcto para cada situación. Un algoritmo O(n²) con millones de datos puede tardar horas donde un O(n log n) tardaría segundos.
La programación es, en esencia, resolver problemas lógicos de forma metódica. Los algoritmos de ordenación son uno de los ejemplos más puros de ese proceso: un problema sencillo de enunciar, con soluciones que van de lo intuitivo a lo elegante, y con consecuencias reales en el rendimiento de cualquier sistema que maneje datos.
¿Conocías alguno de estos algoritmos? ¿Te animarías a diseñar el tuyo propio? Cuéntanos en los comentarios.
