← Volver a los ejercicios

Lo que cuesta quicksort: tres entradas pequeñas

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:

entradaarreglon
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

#nivelrangoantesdespués de particionarqcomparacionesacumulado
Solo aparecen las llamadas que entran al if, en el orden en que se ejecutan. El nivel de la llamada inicial es 1.