Quicksort
Elige un valor, el pivote, y pone los valores menores a su izquierda y los mayores a su derecha. Luego hace lo mismo con cada lado.
- Ω(n log n)
- Θ(n log n)
- O(n²)
- O(log n)
- no
- sí
Mejor caso: cómo crece el tiempo con el tamaño n de la lista cuando la entrada es la más fácil para este algoritmo.
Caso medio: cómo suele crecer el tiempo con n. Con n², el doble de valores tarda unas cuatro veces más; n log n crece mucho más despacio.
Peor caso: el crecimiento con la entrada más difícil. Útil cuando la velocidad nunca debe caer.
Espacio: cuánta memoria extra hace falta además de la lista. 1 son unas pocas variables; n, una copia de la lista.
Estable: dos valores iguales conservan su orden original. Importa al ordenar registros por un solo campo.
Sin memoria extra: ordena dentro de la propia lista, sin una segunda lista.
- comparando
- moviendo
- pivote
- en su lugar final
Prueba esto: Elige una lista invertida. El pivote siempre es el menor o el mayor valor restante, así que un lado queda vacío y el coste sube hacia n².
Cómo funciona
Aquí el pivote es el último valor del rango. De izquierda a derecha, cada valor que no es mayor que el pivote pasa al lado izquierdo con un intercambio. Después el pivote se coloca entre los dos grupos, donde ya no se mueve más. Luego cada lado se ordena de la misma forma.
Cuándo es una buena opción
Es una de las formas más rápidas de ordenar en la práctica y casi no necesita memoria extra. Pero si elige una y otra vez un mal pivote, por ejemplo en una lista ya ordenada, se vuelve lento. Las versiones reales eligen el pivote con más cuidado.