Ordenamiento Burbuja

Teoría

También conocido como método de intercambio directo, consiste en comparar los elementos de una lista, tomando uno por uno, comparándolo con el siguiente y ordenándolo (si es menor se dejan igual, si no se cambian), siguiendo con los demás hasta terminar con todos los elementos y luego realzar este proceso varias veces.

Caso de estudio

Un estudiante quiere ordenar su colección de música por el año de lanzamiento de los álbumes.
Él cuenta con los siguientes discos:

Disco	Año de lanzamiento
Led Zeppelin III	1970
Highway to Hell	1979
The Rolling Stones No. 2	1966
My Generation	1965
Bob Dylan	1962

Nota: los valores en color azul se están comparando, en naranja siguen igual y en verde cambiaron de posición.

1. Se toma el primer disco que es Led Zeppelin III del año 1970 ahora se compara con el segundo Highway to Hell de 1979, como el primero es menor, se dejan igual.

1970-1979-1966-1965-1962
1970-1979-1966-1965-1962

2. Ahora se compara Highway to Hell de 1979 con The Rolling Stones No. 2 de 1966, en este caso el primer álbum es de un año posterior al del segundo, entonces se cambian.

1970-1979-1966-1965-1962
1970-1966-1979-1965-1962

3. Continuamos con Highway to Hell de 1979 pero ahora lo comparamos con My Generation de 1965, el primero es mayor entonces se cambian.

1970-1966-1979-1965-1962
1970-1966-1965-1979-1962

4. Continuamos con My Generation de 1965 y lo comparamos con el último elemento Bob Dylan de 1962, como el primero es mayor entonces se cambian.

1970-1966-1965-1979-1962
1970-1966-1965-1962-1979

¿Cómo vamos?

Disco	Año de lanzamiento
Led Zeppelin III	1970
The Rolling Stones No. 2	1966
My Generation	1965
Bob Dylan	1962
Highway to Hell	1979

Vamos bien pero hay elementos que siguen si organizarse, así que hay que hacer otra pasada, siguiendo el mismo procedimiento.

1. Volvemos a tomar el primer elemento que es “Led Zeppelin III” del año 1970 y lo comparamos con el segundo The Rolling Stones No. 2 de 1966, como el primero es mayor se cambian.

1970-1966-1965-1962-1979
1966-1970-1965-1962-1979

2. Ahora se compara Led Zeppelin III de 1970 con con My Generation de1965, como el primero es mayor se cambian.

1966-1970-1965-1962-1979
1966-1965-1970-1962-1979

3. Seguimos con Led Zeppelin III de 1970 y se compara con Bob Dylan de 1962 como el primero es de un año posterior se cambian.

1966-1965-1970-1962-1979
1966-1965-1962-1970-1979

4. Con Led Zeppelin III de 1970 se compara con Highway to Hell de 1979, como el primero es menor no hacemos ningún cambio.

1966-1965-1962-1970-1979
1966-1965-1962-1970-1979

¿Cómo vamos?

Disco	Año de lanzamiento
The Rolling Stones No. 2	1966
My Generation	1965
Bob Dylan	1962
Led Zeppelin III	1970
Highway to Hell	1979

Vamos bien pero hay elementos que siguen si organizarse, así que hay que hacer otra pasada, siguiendo el mismo procedimiento.

1. Volvemos a tomar el primer elemento que es The Rolling Stones No. 2 de 1966 comparamos con el segundo My Generation 1965, como el primero es mayor se cambian.

1966-1965-1962-1970-1979
1965-1966-1962-1970-1979

2. Volvemos a tomar el primer elemento que es The Rolling Stones No. 2 de 1966 se compara con Bob Dylan de 1962, como el primero es mayor los cambiamos.

1965-1966-1962-1970-1979
1965-1962-1966-1970-1979

3. Volvemos a tomar el primer elemento que es The Rolling Stones No. 2 de 1966 pero ahora comparamos Led Zeppelin III 1970, como el primero es menor entonces los dejamos así.

1965-1962-1966-1970-1979
1965-1962-1966-1970-1979

4. En este punto comparamos Led Zeppelin III 1970 con Highway to Hell de 1979, como el primero es menor no hacemos ningún cambio.

1965-1962-1966-1970-1979
1965-1962-1966-1970-1979

¿Cómo vamos?

Disco	Año de lanzamiento
My Generation	1965
Bob Dylan	1962
The Rolling Stones No. 2	1966
Led Zeppelin III	1970
Highway to Hell	1979

1. Volvemos a tomar el primer elemento que es My Generation 1965 se compara con Bob Dylan de 1962, el primero es mayor así que se cambian.

1965-1962-1966-1970-1979
1962-1965-1966-1970-1979


2. Continuamos con My Generation 1965 se compara The Rolling Stones No. 2 de 1966, como el primero es menor no hacemos ningún cambio.

1962-1965-1966-1970-1979
1962-1965-1966-1970-1979

3. Seguimos con The Rolling Stones No. 2 de 1966 se compara con Led Zeppelin III 1970, como el primero es menor se dejan igual.

1962-1965-1966-1970-1979
1962-1965-1966-1970-1979

4. Ahora Led Zeppelin III 1970 con Highway to Hell de 1979, también se dejan igual.

1965-1962-1966-1970-1979
1965-1962-1966-1970-1979

En este caso fueron necesarias 4 pasadas ósea una menos del número de elementos lo que nos indica que es necesario ejecutar n-1 pasadas y en cada pasada n-1 comparaciones.
Y listo tenemos los álbumes ordenados por año de lanzamiento.

Disco	Año de lanzamiento
Bob Dylan	1962
My Generation	1965
The Rolling Stones No. 2	1966
Led Zeppelin III	1970
Highway to Hell	1979

Notemos como en cada pasada los elemento mayores quedan al final de la lista, lo que significa que ya no es necesario ordenarlos, este es el punto de partida para el algoritmo de burbuja mejorado.

Algoritmo

Para ordenar una lista de números (sin elementos repetidos), de menor a mayor de izquierda a derecha usando “Ordenamiento Burbuja”.

1. Se toma el primer elemento y se compara con el de la derecha.
2. Se evalúa si dicho elemento (1°) es mayor al otro (2°) de ser así se continua en el paso 2.1 de lo contrario en el paso 2.2.
2.1 Se cambian de lugar los elementos garantizando que el menor quede a la izquierda.
2.2 Se dejan los elementos en el mismo orden.
3. Se continua repitiendo el paso uno hasta terminar con todos los elementos.
4. Se realiza el mismo procedimiento de los pasos 1-3 un número de veces igual al número de elementos a ordenar.