Overview
El quicksort elige un pivote, coloca los elementos más pequeños a su izquierda, los más grandes a su derecha, y recurse en ambas partes.
Analogy
Como organizar personas en una fila: elige a alguien como pivote, todos más bajos van a la izquierda, todos más altos a la derecha, repite.
Step-by-step
- Elige un pivote (primer, último o aleatorio)
- Particiona: elementos < pivote van a la izquierda
- Recurse en la partición izquierda y derecha
- La lista está ordenada cuando las particiones tienen tamaño ≤ 1
Visual
[3,6,8,10,1,2,1] pivote=3
→ [1,2,1] 3 [6,8,10]
→ ordena ambas partes
Common mistakes
- Siempre elegir el primer/último elemento como pivote → O(n²) en datos ordenados
- No manejar duplicados — puede llevar a O(n²)
Practice questions
- Implementa partición de Lomuto y Hoare
- Usa pivote aleatorio para evitar el peor caso
Time
O(n log n) promedio, O(n²) peor caso
Space
O(log n) pila de recursión promedio