Algoritmos de ordenamiento comparados

No hay un único algoritmo de ordenamiento más rápido. Algunos son sencillos pero lentos, otros son rápidos con datos aleatorios pero tropiezan con datos ordenados, y algunos ni siquiera ordenan por comparación. Hacer competir a los ocho sobre la misma lista muestra las diferencias de un vistazo.

Ocho carriles de barras, uno por algoritmo de ordenamiento; algunos ya están ordenados y en verde, otros siguen desordenados
Ocho carriles de barras, uno por algoritmo de ordenamiento; algunos ya están ordenados y en verde, otros siguen desordenados

Tres familias

El ordenamiento de burbuja, por selección y por inserción son los ordenamientos sencillos. Comparan e intercambian valores cercanos y necesitan un tiempo proporcional a n² en una lista aleatoria. El ordenamiento por mezcla, quicksort y el ordenamiento por montículos reparten el trabajo con astucia y necesitan un tiempo proporcional a n log n, lo mejor que puede hacer un ordenamiento cuando solo puede preguntar cuál de dos valores es mayor. El ordenamiento radix y el ordenamiento por cuentas se saltan esa pregunta por completo: usan los propios dígitos o valores, lo que solo funciona con claves como números enteros pequeños.

Medir el trabajo

La Carrera de ordenamientos cuenta una operación por cada comparación, cada dígito o valor leído y cada intercambio o movimiento. Con 40 valores aleatorios eso da unas 120 para el ordenamiento por cuentas, 240 para el ordenamiento radix, 260 para quicksort, 380 para el ordenamiento por mezcla, 490 para el de montículos, unas 820 cada uno para el de selección y el de inserción, y más de 1100 para el de burbuja. Los ordenadores reales también dependen de la memoria: en la práctica, quicksort suele ser más rápido de lo que sugiere su cuenta, y el ordenamiento por montículos más lento, por la forma en que recorren la lista.

Los datos de entrada importan

Con una lista casi ordenada, el ordenamiento por inserción solo necesita unas 50 operaciones para 40 valores y el de burbuja unas 90, porque cada valor está cerca de su sitio. Con una lista invertida, esos mismos dos necesitan 1560, su peor caso. Al ordenamiento por selección, por montículos, por mezcla, radix y por cuentas apenas les afecta el orden. Quicksort con la mediana de tres maneja bien las listas ordenadas e invertidas, pero con un pivote ingenuo una lista ordenada es su peor caso. Pocos valores distintos frenan a quicksort, porque los valores iguales van todos al mismo lado.

Memoria y estabilidad

El ordenamiento de burbuja, por selección, por inserción, quicksort y el ordenamiento por montículos trabajan in situ, con poca o ninguna memoria extra. El ordenamiento por mezcla, radix y por cuentas necesitan un búfer tan largo como la lista. Un ordenamiento estable mantiene los valores iguales en su orden original: el de burbuja, por inserción, por mezcla, radix y por cuentas son estables, mientras que el de selección, quicksort y el de montículos no lo son. La estabilidad importa cuando ordenas registros por un campo y luego por otro.

Cuál usar

En la práctica usas el ordenamiento integrado en tu lenguaje de programación: normalmente Timsort, un ordenamiento por mezcla que usa el ordenamiento por inserción para los trozos cortos y es rápido con datos parcialmente ordenados, o introsort, un quicksort que recurre al ordenamiento por montículos y usa el de inserción para las partes pequeñas. Con muchas claves enteras pequeñas, el ordenamiento por cuentas o el radix pueden superar a ambos. El ordenamiento de burbuja y el de selección sirven sobre todo para aprender.

Pruébalo

Abre la Carrera de ordenamientos y pulsa Reproducir. Cada carril es un ordenamiento sobre la misma lista; el número de la derecha cuenta sus operaciones, y un carril se vuelve verde cuando termina. Prueba una lista casi ordenada, una invertida y pocos valores distintos, y mira cómo cambia el orden de llegada. Cada ordenamiento tiene también su propia app, donde puedes seguirlo paso a paso.

Preguntas frecuentes

¿Cuál es el algoritmo de ordenamiento más rápido?

Con datos generales, quicksort y el ordenamiento por mezcla (y los híbridos basados en ellos, como introsort y Timsort) son los más rápidos de media, con n log n. Con claves enteras pequeñas, el ordenamiento por cuentas y el radix son aún más rápidos. Con listas cortas o casi ordenadas, gana el ordenamiento por inserción.

¿Por qué ningún ordenamiento por comparación puede superar n log n?

Una lista de n valores puede estar en n! órdenes, y cada comparación tiene dos resultados, así que hacen falta al menos log₂(n!) comparaciones para distinguirlos todos en el peor caso. Eso es aproximadamente n log₂ n. El ordenamiento radix y el ordenamiento por cuentas evitan este límite porque no comparan.

¿Qué algoritmos de ordenamiento son estables?

El ordenamiento de burbuja, por inserción, por mezcla, radix y por cuentas son estables en sus formas habituales. El ordenamiento por selección, quicksort y el ordenamiento por montículos no lo son, porque mueven valores a grandes distancias.

¿Qué ordenamientos necesitan memoria extra?

El ordenamiento por mezcla, radix y por cuentas necesitan un búfer casi tan largo como la lista. El de burbuja, por selección, por inserción y por montículos casi no necesitan, y quicksort solo un poco para su recursión.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Empezar la Carrera de ordenamientos