El arreglo es a = ⟨3, 8, 1, 6, 9, 2, 5⟩ y se
llama particionar(a, 0, 6). El pivote es el último,
x = a[6] = 5.
1. Antes de correrlo: dónde queda el pivote
Sin seguir el ciclo, ¿qué valor de q
devuelve la función?
2. Vuelta por vuelta
menor o igual que xmayor que xsin revisarpivote
Cada paso muestra el estado en el momento de evaluar la
condición del while, y el texto dice qué hace la vuelta que
sigue. La casilla con borde grueso es a[j], la que se va a
comparar.
3. El arreglo al terminar
¿Cómo queda a[0..6] después del último
intercambio?
4. Las llamadas a intercambiar
Contando todas, también las que cambian una casilla
consigo misma, ¿cuántas veces se llama a intercambiar?
Lo que quedó
Con siete elementos el ciclo da seis vueltas y hace seis
comparaciones, una por vuelta. Intercambia solo cuando encuentra un valor
menor o igual que el pivote, y una vez más al final: a lo sumo
n intercambios, así que particionar cuesta Θ(n)
en tiempo. En espacio aparte usa x, i,
j y el temporal de intercambiar: Θ(1).