Categoría: Algoritmos y estructuras

Bogo sort es el chiste de la informática. La idea: baraja la lista al azar, comprueba si por casualidad ha quedado ordenada, y si no, vuelve a barajar. Y otra vez. Y otra. Hasta que la suerte te sonría. Es el peor algoritmo de ordenación que existe (en su versión “honesta”, la que no está diseñada para ser peor a...

Gnome sort es uno de los algoritmos más curiosos de la familia. La idea es absurdamente simple: imagina un gnomo de jardín ordenando una fila de macetas. Si las dos que tiene delante están bien, da un paso adelante. Si están mal, las intercambia y da un paso atrás. Y repite. Cuando llega al final sin hacer intercambios, el jardín...

Comb sort es lo que pasa cuando alguien mira bubble sort y dice “y si en vez de comparar solo vecinos, comparamos elementos separados por un peine de dientes largos que va menguando?”. Resultado: un algoritmo que rompe el O(n²) puro de bubble y se queda en algo entre Θ(n log n) y O(n²) en la práctica, dependiendo del factor...

Cocktail sort (también conocido como shaker sort o bidirectional bubble sort) es una variante de bubble sort que recorre la lista en zigzag: una pasada de izquierda a derecha empujando el mayor al final, luego una de derecha a izquierda empujando el menor al principio. Cada doble-pasada ordena por los dos extremos a la vez. ¿Lo bueno? Resuelve un problema...

Shell sort es la primera idea brillante de la historia de los algoritmos de ordenación: coger insertion sort, que es lento (O(n²)), y darle saltos para que coloque a grandes rasgos antes de afinar. Resultado: un algoritmo que en la práctica corre mucho más rápido que insertion y queda en una zona difusa entre O(n^1.3) y O(n²) (depende de la...

Radix sort es la extensión natural de counting sort cuando el rango de valores es demasiado grande para counting puro. La idea: en vez de ordenar por el valor entero, ordena dígito a dígito, empezando por el menos significativo. Cada pasada por dígito usa counting sort como subrutina. Resultado: O(d·(n+k)), donde d = nº de dígitos y k = base...

Counting sort es el algoritmo que rompe las reglas del juego. Todos los demás algoritmos del clúster (bubble, quick, merge, heap…) comparan elementos. Por eso están acotados por debajo en Ω(n log n): la información que pueden extraer comparando pares es limitada. Counting NO compara. Cuenta. Y por eso puede ser lineal, Θ(n + k), donde k es el rango...

Selection sort es lo que harías si tuvieras un cajón de calcetines desordenados y los quisieras ordenar por talla: sacas primero el más pequeño, luego el siguiente más pequeño, y así hasta vaciar el cajón. Cada elección es una pasada completa por la parte sin ordenar. Sencillo de explicar, sencillo de programar, y siempre del orden de n² comparaciones —...

Cuando llamas a sorted([3, 1, 4, 1, 5]) en Python, el algoritmo que se ejecuta detrás se llama Timsort. No es quicksort. No es merge sort. No es heapsort. Es un híbrido inteligente que Tim Peters inventó en 2002 específicamente para Python, y que después se ha copiado en JavaScript (V8, desde 2018) y en Java (para objetos, desde 1.7)....

Heapsort es el algoritmo de ordenación que te garantiza O(n log n) siempre sin pedirte memoria extra. Es la solución cuando no quieres ni el peor caso de quicksort (O(n²)) ni la memoria O(n) de merge sort. Y es además la red de seguridad que muchos lenguajes modernos usan dentro de Introsort: si quicksort se atasca, pasan a heapsort. Pero...