← Volver a los ejercicios

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.

ChequeojA[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₀)

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.