ordenarBurbuja: un lema adentro, un teorema afuera
Dos ciclos, uno dentro del otro. El de adentro se demuestra
solo y su conclusión se guarda con nombre propio: un lema. El de afuera no
vuelve a mirar el código de adentro — cita el lema y sigue. Esa es toda la
técnica, y aquí se arma pieza por pieza.
1. La especificación y la predicción
Entrada: un arreglo A[0..N) de números,
N ≥ 1. Salida: el mismo arreglo, ordenado de forma no
decreciente, con los mismos elementos.
Arreglo:
¿Cuántas comparaciones hace la línea 6 en total?
2. Ejecute y mire las dos zonas
Paso 0 de 0
Verde: la cola ya terminada, A[N−i..N). Azul: lo que
el ciclo interno ya recorrió en esta pasada. El recuadro marca la
pareja (j, j+1) que se está comparando.
Pruebe [1, 2, 3, 4], que ya viene ordenado: el
algoritmo hace exactamente las mismas comparaciones que con
[4, 3, 2, 1]. Este ciclo no se entera de que ya terminó, y eso se ve en
la cuenta de la tarjeta 1.
3. La traza del ciclo interno
Una fila por chequeo del while de la
línea 5, dentro de la pasada que está corriendo ahora
(i = –). Al cambiar de pasada la tabla
arranca de nuevo.
Chequeo
j
A[0..j]
A[j]
¿Qué se repite?
4. El invariante del ciclo interno
Mire la columna A[j] contra la columna A[0..j],
fila por fila. Y escríbalo en términos de N, i, j y A: no de los números
de este arreglo.
¿Qué se cumple en cada chequeo de la línea 5? (ese será J₁)
¿Hasta dónde llega j? (ese será J₀)
Lema 1. Al terminar el ciclo interno de la línea 5, la posición
N−1−i contiene el máximo de A[0..N−1−i].
Sale de intersecar la condición rota (j ≥ N−1−i) con J₀ (j ≤ N−1−i), que
deja j = N−1−i, y de sustituir ese valor en J₁. Ese enunciado es todo lo
que el ciclo externo va a necesitar: de aquí en adelante nadie vuelve a
mirar las líneas 5 a 10.
5. El invariante del ciclo externo
Primero encuentre
el invariante de adentro: el de afuera se escribe sobre la conclusión del
lema.
¿Qué se cumple en cada chequeo de la línea 3?
Falta un invariante más, y sin él
el teorema no dice nada útil. ¿Cuál?
6. La demostración
Complete las tarjetas
4 y 5. Se demuestra primero el Lema 1 (los invariantes del ciclo
interno) y después el Teorema 1 (los del externo), que lo cita.
Lema 1, estabilidad: ¿por qué después del cuerpo la posición j+1 tiene el máximo de A[0..j+1]?
Se toma un chequeo arbitrario con j = t y se
asume J₀ y J₁ evaluados en t. Las líneas 6 a 9 dejan en la posición
t+1 el mayor entre A[t] y A[t+1] y en la posición t el menor —si ya
estaban en ese orden no hacen nada, y si no, los intercambian—. Por J₁,
A[t] era el máximo de A[0..t], de modo que el mayor entre A[t] y A[t+1]
es el máximo de A[0..t+1]. La línea 10 deja j = t+1, y entonces A[j] es
el máximo de A[0..j]: J₁ evaluado en t+1. ✓ J₀ vale porque
t < N−1−i implica 0 ≤ t+1 ≤ N−1−i. ✓ Y el intercambio no crea ni
borra elementos: el arreglo sigue siendo una permutación del que entró. ✓
Teorema 1, estabilidad: la pasada i acaba de terminar. ¿Por qué la cola crece en una posición?
Se toma un chequeo arbitrario con i = t, t < N−1,
y se asumen los invariantes evaluados en t. El ciclo interno solo toca
posiciones hasta N−1−t, así que la cola A[N−t..N) queda intacta y sigue
ordenada.
Por el Lema 1, al terminar esa pasada A[N−1−t] es el máximo de
A[0..N−1−t]. La cola nueva es A[N−1−t..N), o sea ese elemento seguido de
la cola vieja. Está ordenada porque A[N−1−t] pertenece a A[0..N−t), y el
segundo invariante evaluado en t dice que todo elemento de A[0..N−t) es
≤ todo elemento de la cola vieja; en particular es ≤ el primero de ella. ✓
Y el segundo invariante se mantiene: todo elemento de A[0..N−1−t) es
≤ A[N−1−t] por el lema, y ≤ todo lo de la cola vieja por hipótesis. ✓
La permutación se conserva porque lo único que hizo el ciclo interno
fueron intercambios. ✓ Las cotas valen porque t < N−1 implica
0 ≤ t+1 ≤ N−1. ✓
Fíjese en lo que no aparece aquí: ni una línea del ciclo interno.
Ya se demostró aparte y ahora se cita.
Teorema 1, terminación: ¿con qué valor de i termina el ciclo externo?
Al salir, la condición i < N−1 es falsa, o sea
i ≥ N−1; intersecando con el invariante de cotas, que da i ≤ N−1, queda
i = N−1. Sustituyendo ese valor: A[N−(N−1)..N) = A[1..N) está ordenado, y
todo elemento de A[0..1) —es decir, A[0]— es ≤ todo elemento de A[1..N).
Un arreglo cuyo primer elemento no supera a ninguno de los demás y cuyo
resto está ordenado, está ordenado. Con la permutación, esa es
exactamente la poscondición. ∎
Teorema 2. La invocación ordenarBurbuja(A) devuelve
A ordenado de forma no decreciente, con los mismos elementos.
Demostración: por el Teorema 1 los invariantes del ciclo externo
se cumplen; la terminación deja i = N−1 y sustituir ese valor da la
poscondición. ∎
El orden de la escritura es lo que hay que retener: primero el lema, que
se demuestra sin saber nada del ciclo de afuera; después el teorema, que
se demuestra sin volver a abrir el de adentro. Si al escribir el externo
aparece un «y entonces el ciclo interno recorre…», es que el lema quedó
mal enunciado.
7. El costo
La pasada número i hace N−1−i comparaciones, y hay
pasadas para i = 0, 1, …, N−2. Sumando:
(N−1) + (N−2) + … + 2 + 1 = N(N−1)/2 ∈ Θ(N²)
La cuenta no depende de los datos: ninguna comparación se ahorra cuando
el arreglo ya viene ordenado, y por eso el mejor caso y el peor caso valen
lo mismo. El ordenamiento por selección de la clase suma exactamente igual.
8. Para llevarse
Sin solución aquí. Agregue una variable
hubo que registre si la pasada hizo algún intercambio, y
termine el ciclo externo cuando una pasada no intercambie nada. Después:
¿cuál es el nuevo invariante del ciclo externo —el viejo ya no alcanza—,
por qué es correcto detenerse ahí, y cuánto cuesta ahora el mejor caso en
términos de N? Cuidado con el reflejo de usar break: se pide
una condición compuesta en el while.