Ordenamiento de burbuja
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.
Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas «burbujas».
La burbuja son dos términos de la lista seguidos, j y j+1, que se comparan: si el primero es mayor que el segundo sus valores se intercambian.
Esta comparación se repite en el centro de los dos bucles, dando lugar a una lista ordenada.
Puede verse que el número de repeticiones solo depende de n y no del orden de los términos, esto es, si pasamos al algoritmo una lista ya ordenada, realizará todas las comparaciones exactamente igual que para una lista no ordenada.
Para el caso del ejemplo, tenemos que: Para la primera iteración del primer bucle: y j tomará los valores de 0 hasta 3: Cuando j vale 0, se comparan
Se repite el proceso hasta que j valga 3, dando lugar a una lista parcialmente ordenada.
Ahora i vale 3, y j hará un recorrido de 0 a 2.
Puede verse que los dos valores más altos ya ocupan su lugar.
No se ha realizado ninguna comparación con el término cuarto, dado que ya se sabe que después del primer ciclo es el mayor de la lista.
Ahora ya i vale 4 y j recorrerá los valores de 0 a 1.
Desde esta nueva ordenación, j pasa a valer 1, con lo que se comparan los términos
En este caso la burbuja ha ascendido menos que en los casos anteriores, y la lista está ya ordenada, pero el algoritmo tendrá que completarse, realizando una última iteración.
Los bucles finalizan y también el procedimiento, dejando la lista ordenada.
El número de intercambios i(n), que hay que realizar depende del orden de los términos y podemos diferenciar, el caso mejor, si el arreglo está previamente ordenado, y el caso peor, si el arreglo está ordenado en orden inverso: Por lo que no se puede determinar una cota ajustada asintótica del número de intercambios, dado que éste dependerá del orden del arreglo en cuestión.
Si pasamos al algoritmo un arreglo ordenado en orden inverso realizará un número de comparaciones: Como ya hemos dicho anteriormente, y tendrá que realizar un número igual de intercambios entre los términos del arreglo, dado que en cada comparación los términos estarán desordenados, y se realizará el intercambio.
En este caso el número de comparaciones será el mismo que en cualquier otro caso: La cota inferior asintótica del número de comparaciones pertenece al orden de n cuadrado, como en los demás casos, pero en todas las comparaciones el orden es el correcto y por tanto no se realiza ningún intercambio: Por lo tanto el coste de intercambios no depende de n, y es constante: El ordenamiento de burbuja tiene una complejidad Ω(n²) igual que ordenamiento por selección.
Cuando una lista ya está ordenada, a diferencia del ordenamiento por inserción que pasará por la lista una vez y encontrará que no hay necesidad de intercambiar las posiciones de los elementos, el método de ordenación por burbuja está forzado a pasar por dichas comparaciones, lo que hace que su complejidad sea cuadrática en el mejor de los casos.
Los elementos mayores al principio de la lista son rápidamente movidos hacia abajo, mientras los elementos menores en el fondo de la lista se mueven a la parte superior muy lentamente.
Esto llevó a nombrar estos elementos conejos y tortugas, respectivamente.
Se han realizado varios esfuerzos para eliminar las tortugas y mejorar la velocidad del ordenamiento de burbuja, la cual será más redonda que nunca.
El ordenamiento por combinación compara los elementos primero en pedazos grandes de la lista, moviendo tortugas extremadamente rápido, antes de proceder a pedazos cada vez más pequeños para alisar la lista.
Resultados experimentales como los descubiertos por Astrachan han demostrado que el ordenamiento por inserción funciona considerablemente mejor incluso con listas aleatorias.
Tomemos como ejemplo los números: "9 6 5 8 2 1", que serán ordenados de menor a mayor valor usando el método burbuja.
( 5 6 8 2 1 9 ), como estos elementos ya están en orden, el algoritmo no hace cambios.
[3] Más tarde fue redescubierto y popularizado por Stephen Lacey y Richard Box con un artículo de Byte Magazine publicado en abril de 1991.
La idea básica es eliminar las tortugas, o valores pequeños cerca del final de la lista, ya que en una ordenación por burbujas éstos ralentizan enormemente la ordenación.
(Conejos, valores grandes al principio de la lista, no suponen un problema en la ordenación por burbujas) Esto se consigue intercambiando inicialmente los elementos que están a cierta distancia unos de otros en la matriz, en lugar de intercambiar sólo los elementos si son adyacentes, y luego reduciendo la distancia elegida hasta que funciona como una ordenación por burbujas normal.
Por lo tanto, si Shellsort se puede considerar como una versión generalizada de la ordenación por inserción que intercambia elementos espaciados a cierta distancia unos de otros, la ordenación por peine se puede considerar como la misma generalización aplicada a la ordenación por burbujas.
