Se cuenta una comparación por cada evaluación de
a[j] <= x dentro de particionar, sumando todas
las llamadas de quicksort(a, 0, n − 1). Las tres entradas
son:
entrada
arreglo
n
ordenada
⟨2, 5, 8, 11, 14, 17⟩
6
al revés
⟨17, 14, 11, 8, 5, 2⟩
6
balanceada
⟨14, 2, 20, 17, 8, 5, 11⟩
7
1. La entrada ordenada
2. La misma entrada al revés
3. La entrada balanceada
Tiene un elemento más que las otras dos.
4. La pila de llamadas
¿Cuántas llamadas a quicksort llegan
a estar abiertas al mismo tiempo? Cuente la inicial y también las de rango
vacío o de un elemento, que abren su registro aunque no entren al
if.
Con la entrada ordenada
Con la entrada balanceada
5. Las llamadas, una por una
#
nivel
rango
antes
después de particionar
q
comparaciones
acumulado
Solo aparecen las llamadas que entran al
if, en el orden en que se ejecutan. El nivel de la llamada
inicial es 1.
Lo que quedó
Seis elementos ordenados cuestan 15 comparaciones y siete
balanceados cuestan 10: el que tiene más datos hace menos trabajo. Lo que
decide el costo no es n sino dónde cae cada pivote. Cuando cae en un
extremo, el total es n(n − 1)/2 y la pila guarda n registros; cuando cae
en la mitad, cada nivel suma a lo sumo n − 1 comparaciones y hay unos
log₂ n niveles, Θ(n log n) en tiempo y Θ(log n) en la pila.