Categoría: Algoritmos y estructuras

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...

Insertion sort es el algoritmo que hace lo mismo que tú cuando ordenas cartas en la mano: coges la siguiente y la deslizas hacia la izquierda hasta dejarla en su sitio entre las que ya tienes ordenadas. Sencillo, didáctico y, sorpresa, rapidísimo cuando la lista ya está casi ordenada — por eso los algoritmos modernos lo usan por dentro para...

Merge sort es el algoritmo de ordenación que da una garantía absoluta: ordena en O(n log n) siempre, da igual la entrada. Sin sorpresas, sin peor casos catastróficos como quicksort, sin sensibilidad a si la lista ya estaba casi ordenada. Ese determinismo lo convierte en la opción correcta cuando importa la previsibilidad: backends serios, ordenaciones estables, escenarios donde “casi siempre...

Bubble sort es el algoritmo de ordenación más sencillo de entender, el primero que enseñan en clase y, a la vez, uno de los más lentos que existen. Si tuvieras que ordenar una fila de personas por altura comparando solo a cada una con la de al lado e intercambiándolas cuando estén descolocadas, eso es exactamente lo que hace bubble...

Quicksort es el algoritmo de ordenación más famoso del mundo, y también el más malinterpretado. Casi todo el mundo te dirá que es “el algoritmo de ordenación más rápido”. La verdad es más interesante: quicksort puro casi ningún lenguaje moderno lo usa tal cual, porque tiene un peor caso O(n²) catastrófico. Lo que usan los lenguajes son híbridos construidos encima...