1 Ordenamiento Burbuja (Bubblesort)

[Volver a Algoritmos] [2 Selección]

1. Descripción.

Este es el algoritmo más sencillo probablemente. Ideal para empezar. Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se intercambian. ¿Sencillo no?

2. Pseudocódigo en C.

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;
 

3. Un 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

4. Optimizando.

Se pueden realizar algunos cambios en este algoritmo que pueden mejorar su rendimiento.

5. Análisis del algoritmo.

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

Ventajas:

Desventajas:

Este algoritmo es uno de los más pobres en rendimiento. Si miras la demostración te darás cuenta de ello. No es recomendable usarlo. Tan sólo está aquí para que lo conozcas, y porque su sencillez lo hace bueno para empezar. Ya veremos otros mucho mejores. Ahora te recomiendo que hagas un programa y lo pruebes. Si tienes dudas mira el programa de ejemplo.

[Volver a Algoritmos] [2 Selección]


©2001 - Julián Hidalgo