← Volver a los ejercicios

Lo que cuesta quicksort: el peor caso

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?