Quicksort es un algoritmo de ordenamiento divide-and-conquer que elige un pivot, particiona elementos en los menores y mayores que este, y luego ordena recursivamente cada lado. Promedio O(n log n), peor caso O(n²).
La partición coloca el pivot en su posición final ordenada; todo a la izquierda es menor, todo a la derecha es mayor. Recurre en ambos lados.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # pick a pivot
left = [x for x in arr if x < pivot] # smaller
mid = [x for x in arr if x == pivot] # equal
right = [x for x in arr if x > pivot] # larger
return quicksort(left) + mid + quicksort(right)
quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
(Se utiliza partición in-place en la práctica para ahorrar memoria.)
| Caso | Tiempo | Causa |
|---|---|---|
| Mejor/Promedio | O(n log n) | particiones balanceadas |
| Peor | O(n²) | ya ordenado con pivot malo |
Quicksort in-place utiliza O(log n) espacio de pila.
Normalmente el más rápido en la práctica debido a amigabilidad con cache y bajo overhead, y es in-place. El peor caso O(n²) se evita con un pivot aleatorizado o median-of-three. No es estable.
Quicksort es el predeterminado en muchas bibliotecas estándar debido a su excelente velocidad de caso promedio y bajo uso de memoria.
Entender por qué la elección del pivot causa el peor caso O(n²) enseña una lección clave: el caso promedio y el peor caso pueden divergir marcadamente.
Es un tema favorito de entrevista precisamente por esa sutileza.