Ordenamiento Tipo Burbuja

ORDENAMIENTO TIPO BURBUJA

La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada, es decir, consiste en evaluar pares de elementos contiguos del arreglo y si el primero es mayor que el siguiente los intercambia (los más chicos quedan abajo). Todo ésto sucede dentro de dos ciclos for que recorren el arreglo. El ciclo más interno realiza las comparaciones, y se asegura ya en la primera pasada completa que el elemento más grande del arreglo suba a la posición más alta (ésto más adelante nos permitirá desarrollar un algorítmo mejorado del método burbuja).

Tabla de variables

Nombre Tipo Uso

lista Cualquiera Lista a ordenar

TAM Constante entera Tamaño de la lista

i Entero Contador

j Entero Contador

temp El mismo que los elementos de la lista Para realizar los intercambios

1. for (i=1; i<TAM; i++)

2. for j=0 ; j<TAM - 1; j++)

3. if (lista[j] > lista[j+1])

4. temp = lista[j];

5. lista[j] = lista[j+1];

6. lista[j+1] = temp;

Ejemplo

Vamos a ver un ejemplo. Esta es nuestra lista:

4 - 3 - 5 - 2 - 1

Tenemos 5 elementos. Es decir, TAM toma el valor 5. Comenzamos comparando el primero con el segundo elemento. 4 es mayor que 3, así que intercambiamos. Ahora tenemos:

3 - 4 - 5 - 2 - 1

Ahora comparamos el segundo con el tercero: 4 es menor que 5, así que no hacemos nada. Continuamos con el tercero y el cuarto: 5 es mayor que 2. Intercambiamos y obtenemos:

3 - 4 - 2 - 5 - 1

Comparamos el cuarto y el quinto: 5 es mayor que 1. 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

ANALISIS DEL ALGORITMO

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 sólo requiere de una variable adicional 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 es n * n = O(n2). El comportamiento del caso promedio depende del orden de entrada de los datos, pero es sólo un poco mejor que el del peor caso, y sigue

...