Cómo funciona
Se elige un pivote, aquí el último elemento del rango. Un índice j recorre el rango:
cada elemento ≤ pivote se intercambia hacia una zona que crece por la izquierda (termina en i); los
mayores quedan detrás. Al final, el pivote se intercambia con el primero de los mayores y queda en su
posición definitiva: todo lo de su izquierda es menor o igual y todo lo de su derecha,
mayor.
Después se repite con cada lado. Los corchetes bajo la regla son la pila de llamadas:
el rango que se está partiendo y los que esperan su turno.
Paso a paso con [5, 3, 8, 1, 4]
- 01Rango 0‥4, pivote 4: 5 > 4 se queda; 3 ≤ 4 se intercambia con el 5 →
[3, 5, 8, 1, 4]; 8 > 4; 1 ≤ 4 se intercambia con el 5 → [3, 1, 8, 5, 4]. El pivote se intercambia con el 8 → [3, 1, 4, 5, 8]: el 4 ya está en su sitio. 4 comparaciones, 3 intercambios.
- 02Rango 0‥1, pivote 1: 3 > 1; el pivote se intercambia con el 3 →
[1, 3, 4, 5, 8]. El 3 queda solo en su rango: ya está en su sitio.
- 03Rango 3‥4, pivote 8: 5 ≤ 8, la zona de menores crece sin intercambiar; el 8 ya estaba detrás de ella. El 5 queda solo.
- ΣTotal: 3 particiones, 6 comparaciones y 4 intercambios. Bubble Sort, con el mismo array, haría 10 comparaciones y 6 intercambios.
Por qué es rápido… casi siempre
Partir un rango cuesta una comparación por elemento. Si el pivote lo divide por la mitad, hay unos
log₂ n niveles de recursión con n comparaciones cada uno: n·log n. Además trabaja en el
propio array y sus intercambios son locales, por eso en la práctica suele ganar a Merge Sort y Heap Sort.
Con un array ya ordenado, el último elemento es el máximo: cada partición solo aparta al
pivote, la recursión baja n niveles y hace n(n−1)/2 comparaciones, como Bubble Sort. Las
implementaciones reales lo evitan eligiendo el pivote al azar o como la mediana de tres elementos.
Complejidad
- Mejor caso
- O(n log n)
- Caso promedio
- O(n log n)
- Peor caso
- O(n²)
- Espacio extra
- O(log n) (pila)
- Estable
- No
- In situ
- Sí