Quicksort

El quicksort, u ordenamiento rápido, es uno de los algoritmos de ordenamiento más usados. Elige un pivote, divide la lista en los valores menores que el pivote y el resto, y ordena los dos lados de la misma forma. Es rápido en la práctica y no necesita una lista adicional, pero su rapidez depende del pivote.

Barras particionadas alrededor de una barra pivote: las menores a un lado, las mayores al otro y el pivote entre ellas
Barras particionadas alrededor de una barra pivote: las menores a un lado, las mayores al otro y el pivote entre ellas

La idea

Elige un valor como pivote. Reorganiza la lista para que cada valor menor que el pivote quede antes de él y todos los demás después. Esa reorganización se llama partición, y deja el pivote justo donde le corresponde en la lista ordenada. Los dos lados son ahora problemas independientes: ordena cada uno con quicksort. Un lado con un solo valor o ninguno ya está ordenado.

La partición, paso a paso

La aplicación usa la partición de Lomuto. El pivote se mueve al final de la parte. Un marcador empieza al principio: todo lo que hay antes de él es menor que el pivote. Cada uno de los demás valores se compara con el pivote; si es menor, se intercambia a la posición del marcador y el marcador avanza un lugar. Al final, el pivote se intercambia a la posición del marcador. Toma 5, 1, 4, 2, 8 con el último valor como pivote: los cuatro valores son menores que 8, así que 8 se queda al final. La parte 5, 1, 4, 2 se particiona alrededor de 2, lo que da 1, 2, 4, 5, y 4, 5 alrededor de 5. Son 8 comparaciones, 2 intercambios y 3 particiones.

Pivotes buenos y malos

Si cada pivote cayera en el centro, cada partición dividiría el problema por la mitad, y la ordenación necesitaría unas n log₂ n comparaciones. En una lista aleatoria los pivotes rara vez son perfectos, pero suelen ser bastante buenos: para 40 valores aleatorios la aplicación cuenta unas 190 comparaciones. El peor caso se da cuando el pivote es siempre el valor más pequeño o el más grande. Con el último valor como pivote, una lista ya ordenada, o invertida, hace justo eso: cada partición solo quita el pivote, y la ordenación necesita n(n − 1)/2 comparaciones, 780 para 40 valores.

Cómo elegir el pivote

Un pivote aleatorio hace que el peor caso sea extremadamente improbable con cualquier entrada, porque ningún orden concreto puede engañarlo. La mediana de tres, el valor central entre el primer elemento, el del medio y el último, es barata y maneja bien las listas ordenadas e invertidas. Prueba ambos con una lista ordenada en la aplicación y las comparaciones bajan de 780 a unas 150. Muchos valores iguales son otro problema: todos caen al mismo lado del pivote. Una partición en tres partes, que guarda los valores iguales al pivote en una parte central, lo soluciona.

Historia y uso

Tony Hoare inventó el quicksort en 1959 y lo publicó en 1961. Su propia partición recorre la lista desde ambos extremos y hace menos intercambios; la versión más sencilla de Lomuto, la que se muestra aquí, se hizo popular gracias a los libros de texto. El quicksort ordena in situ y su bucle interno es muy corto, así que en la práctica suele ser más rápido que el ordenamiento por mezcla, aunque no es estable. Introsort, el algoritmo de ordenamiento de la biblioteca estándar de C++, ejecuta quicksort y pasa al ordenamiento por montículos si las particiones se vuelven demasiado desiguales, así que su peor caso sigue siendo n log n.

Tony Hoare, que inventó el ordenamiento rápido en 1959 y lo publicó en 1961.
Tony Hoare, que inventó el ordenamiento rápido en 1959 y lo publicó en 1961.

Explóralo

Abre la aplicación y pulsa Paso. La parte que se particiona aparece sombreada, el pivote tiene su propio color y la línea discontinua marca el final de la parte izquierda, la de los valores menores que el pivote. Cada pivote se vuelve verde cuando llega a su lugar definitivo. Elige una lista ordenada y el último valor como pivote, cambia después a la mediana de tres y compara los contadores.

Preguntas frecuentes

¿Cuál es la complejidad temporal del quicksort?

O(n log n) de media y con buenos pivotes, O(n²) en el peor caso. Ordena in situ; la recursión necesita O(log n) de memoria adicional si se ordena primero el lado más pequeño.

¿Qué diferencia hay entre la partición de Lomuto y la de Hoare?

Lomuto usa un solo marcador y recorre la lista de izquierda a derecha, lo que es fácil de seguir y es lo que muestra esta aplicación. Hoare recorre la lista desde ambos extremos hacia el centro e intercambia los pares que están en el lado equivocado, lo que hace de media unas tres veces menos intercambios.

¿Por qué el quicksort es lento cuando muchos valores son iguales?

Los valores iguales al pivote van todos al mismo lado, así que una lista con pocos valores distintos se divide de forma desigual, y una lista de valores iguales es tan mala como el peor caso. Una partición en tres partes que reúne en el centro los valores iguales al pivote lo evita.

¿Es estable el quicksort?

No. Los intercambios durante una partición mueven valores a mucha distancia, así que valores iguales pueden cambiar de orden.

¿Listo para probarlo?

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

Probar quicksort