Ensayos

ORDENACIÓN POR BURBUJA
El método de ordenación por burbuja es el más conocido y popular entre estudiantes y aprendices
de programación, por su facilidad de comprensión y programación; por el contrario, es el menos
eficiente y por ello, normalmente, se aprende su técnica pero no suele utilizarse.
La técnica utilizada se denomina ordenación por burbuja u ordenación por hundimiento debido
a quelos valores más pequeños «burbujean» gradualmente (suben) hacia la cima o parte superior
del array de modo similar a como suben las burbujas en el agua, mientras que los valores mayores
se hunden en la parte inferior del array. La técnica consiste en hacer varias pasadas a través del
array. En cada pasada, se comparan parejas sucesivas de elementos. Si una pareja está en orden
creciente (olos valores son idénticos), se dejan los valores como están. Si una pareja está en orden
decreciente, sus valores se intercambian en el array.

6.6.1. Algoritmo de la burbuja
En el caso de un array (lista) con n elementos, la ordenación por burbuja requiere hasta n − 1 pasadas.
Por cada pasada se comparan elementos adyacentes y se intercambian sus valores cuando el
primer elemento es mayor queel segundo elemento. Al final de cada pasada, el elemento mayor ha
«burbujeado» hasta la cima de la sublista actual. Por ejemplo, después que la pasada 0 está completa,
la cola de la lista A[n − 1] está ordenada y el frente de la lista permanece desordenado. Las etapas
del algoritmo son:
• En la pasada 0 se comparan elementos adyacentes:
(A[0],A[1]),(A[1],A[2]),(A[2],A[3]),...(A[n-2],A[n-1])Se realizan n − 1 comparaciones, por cada pareja (A[i],A[i+1]) se intercambian los
valores si A[i+1] < A[i]. Al final de la pasada, el elemento mayor de la lista está situado en
A[n-1].
• En la pasada 1 se realizan las mismas comparaciones e intercambios, terminando con el
elemento segundo mayor valor en A[n-2].
• El proceso termina con la pasada n − 1, en la que el elemento más pequeñose almacena en
A[0].
174 Algoritmos y estructuras de datos
El algoritmo tiene una mejora inmediata, el proceso de ordenación puede terminar en la pasada
n − 1, o bien antes, si en una pasada no se produce intercambio alguno entre elementos del vector es
porque ya está ordenado, entonces no es necesario más pasadas.
El ejemplo siguiente ilustra el funcionamiento del algoritmo de la burbujacon un array de 5
elementos (A = 50, 20, 40, 80, 30), donde se introduce una variable interruptor para detectar
si se ha producido intercambio en la pasada.
Pasada 0 50 20 40 80 30 Intercambio 50 y 20
mbbb⁄
Pasada 0 20 50 40 80 30 Intercambio 50 y 40
mbbb⁄
Pasada 0 20 40 50 80 30 50 y 80 ordenados
mbbb⁄
Pasada 0 20 40 50 80 30 Intercambio 80 y 30
mbbb⁄
Pasada 0 20 40 50 30 80
• Elementomayor es 80
• interruptor = TRUE
En la pasada 1:
Pasada 0 20 40 50 30 80 20 y 40 ordenados
mbbb⁄
Pasada 0 20 40 50 30 80 40 y 50 ordenados
mbbb⁄
Pasada 0 20 40 50 30 80 Se intercambian 50 y 30
mbbb⁄
Pasada 0 20 40 30 50 80
• 50 y 80 elementos mayores y ordenados
• interruptor = TRUE
En la pasada 2, sólo se hacen dos comparaciones:
Pasada 0 20 40 30 50 80 20 y 40 ordenados
mbbb⁄Pasada 0 20 30 40 50 80
• Se intercambian 40 y 30
• interruptor = TRUE
mbbb⁄
Algoritmos de ordenación y búsqueda 175
En la pasada 3, se hace una única comparación de 20 y 30, y no se produce intercambio:
Pasada 0 20 30 40 50 80 20 y 30 ordenados
mbbb⁄
Pasada 0 20 30 40 50 80
• Lista ordenada
• interruptor = FALSE
En consecuencia, el algoritmo de ordenación de burbuja mejorado contempla dosbucles anidados:
el bucle externo controla la cantidad de pasadas (al principio de la primera pasada todavía no se
ha producido ningún intercambio, por tanto la variable interruptor se pone a valor falso (0); el
bucle interno controla cada pasada individualmente y cuando se produce un intercambio, cambia el
valor de interruptor a verdadero (1).
El algoritmo terminará, bien cuando se termine...