Cuatro arreglos con los mismos siete valores, 3, 6, 9, 12,
15, 18 y 21, en distinto orden. Se ordenan con el quicksort de
la sesión, con el pivote en el último lugar, y se cuentan las evaluaciones
de a[j] <= x.
1. ¿Cuál cuesta más?
2. La cuenta de A
¿Cuántas comparaciones hace con A?
3. Qué hace caro a A
4. El pivote del medio
Antes de cada particionar se cambia
a[(ini + fin) / 2] con a[fin], y
particionar queda igual. ¿Cuántas comparaciones hace ahora
sobre A?
5. Ninguna entrada fija
Se quiere que ninguna entrada, escogida de
antemano, provoque siempre el peor caso. ¿Qué pivote lo consigue?
Lo que quedó
El peor caso no lo marca el aspecto de la entrada sino
dónde cae cada pivote. A no parece ordenada y cuesta lo mismo que una
ordenada, 21 comparaciones, porque en cada llamada el último es un extremo;
B parece casi ordenada y cuesta menos. Cambiar la casilla del pivote no
toca particionar: es un intercambio de Θ(1) antes de
llamarla, y escogerla al azar deja el tiempo esperado en Θ(n log n) para
cualquier entrada.