Estructura de datos: algoritmo de clasificación de burbujas
La clasificación de burbujas es un algoritmo de clasificación simple. Este algoritmo de clasificación es un algoritmo basado en la comparación en el que cada par de elementos adyacentes se compara y los elementos se intercambian si no están en orden. Este algoritmo no es adecuado para grandes conjuntos de datos ya que su complejidad promedio y en el peor de los casos son de Ο (n 2 ) donden es el número de elementos.
¿Cómo funciona Bubble Sort?
Tomamos una matriz sin clasificar para nuestro ejemplo. La clasificación de burbujas lleva Ο (n 2 ) tiempo, por lo que la mantenemos breve y precisa.
La clasificación de burbujas comienza con los dos primeros elementos, comparándolos para comprobar cuál es mayor.
En este caso, el valor 33 es mayor que 14, por lo que ya está en ubicaciones ordenadas. A continuación, comparamos 33 con 27.
Encontramos que 27 es menor que 33 y estos dos valores deben intercambiarse.
La nueva matriz debería verse así:
A continuación, comparamos 33 y 35. Encontramos que ambos están en posiciones ya ordenadas.
Luego pasamos a los siguientes dos valores, 35 y 10.
Entonces sabemos que 10 es más pequeño que 35. Por lo tanto, no están ordenados.
Intercambiamos estos valores. Descubrimos que hemos llegado al final de la matriz. Después de una iteración, la matriz debería verse así:
Para ser precisos, ahora mostramos cómo debería verse una matriz después de cada iteración. Después de la segunda iteración, debería verse así:
Observe que después de cada iteración, al menos un valor se mueve al final.
Y cuando no se requiere intercambio, las clasificaciones de burbujas aprenden que una matriz está completamente ordenada.
Ahora deberíamos analizar algunos aspectos prácticos de la clasificación de burbujas.
Algoritmo
Asumimos list es una matriz de nelementos. Además asumimos queswap función intercambia los valores de los elementos de matriz dados.
begin BubbleSort(list)
for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSortPseudocódigo
Observamos en el algoritmo que Bubble Sort compara cada par de elementos de la matriz a menos que toda la matriz esté completamente ordenada en orden ascendente. Esto puede causar algunos problemas de complejidad, como qué pasa si la matriz no necesita más intercambio, ya que todos los elementos ya están ascendiendo.
Para aliviar el problema, usamos una variable de marca swappedlo que nos ayudará a ver si se ha producido algún cambio o no. Si no se ha producido ningún intercambio, es decir, la matriz no requiere más procesamiento para ser ordenada, saldrá del ciclo.
El pseudocódigo del algoritmo BubbleSort se puede escribir de la siguiente manera:
procedure bubbleSort( list : array of items )
loop = list.count;
for i = 0 to loop-1 do:
swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */
if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if
end for
/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped) then
break
end if
end for
end procedure return listImplementación
Un problema más que no abordamos en nuestro algoritmo original y su pseudocódigo improvisado, es que, después de cada iteración, los valores más altos se establecen al final de la matriz. Por tanto, la siguiente iteración no necesita incluir elementos ya ordenados. Para ello, en nuestra implementación, restringimos el ciclo interno para evitar valores ya ordenados.
Para conocer la implementación de la clasificación de burbujas en el lenguaje de programación C, haga clic aquí .