Page 59 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

donde

lista: Es cualquier lista para ordenar.

TAM: Es una constante que determina el tamaño de la lista.

i, j: Contadores.

temp: Variable que permite realizar los intercambios de la lista.

Veamos un ejemplo. Esta es nuestra lista:

4 - 3 - 5 - 2 – 1.

Tenemos cinco elementos; por tanto, TAM toma el valor 5. Comenzamos comparando el primer ele-
mento con el segundo: 4 es mayor que 3, así que intercambiamos. Ahora tenemos:

3 - 4 - 5 - 2 – 1.

Luego comparamos el segundo con el tercero: 4 es menor que 5, así que no hacemos nada. Segui-
mos con el tercero y el cuarto: 5 es mayor que 2, por tanto, intercambiamos y obtenemos:

3 - 4 - 2 - 5 – 1.

Comparamos el cuarto y quinto elemento: 5 es mayor que 1, así que intercambiamos nuevamente:

3 - 4 - 2 - 1 – 5.

Repitiendo este proceso, vamos obteniendo los siguientes resultados:

3 - 2 - 1 - 4 - 5

2 - 1 - 3 - 4 - 5

1 - 2 - 3 - 4 - 5

Este es el análisis para la versión no optimizada del algoritmo:

• Estabilidad: Este algoritmo nunca intercambia registros con claves iguales. Por
lo tanto, es estable.

• Requerimientos de memoria: Este algoritmo solo requiere de una variable adi-
cional para realizar los intercambios.

• Tiempo de ejecución: El ciclo interno se ejecuta n veces para una lista de n
elementos. El ciclo externo también se ejecuta n veces. Es decir, la complejidad

53