La clasificación de burbujas es un algoritmo simple que se utiliza para clasificar un conjunto dado de n elementos proporcionados en forma de una matriz con n número de elementos. Bubble Sort compara todos los elementos uno por uno y los clasifica según sus valores.
Si la matriz dada tiene que ser ordenada en orden ascendente, entonces la bubble sort comenzará comparando el primer elemento de la matriz con el segundo elemento, si el primer elemento es mayor que el segundo elemento, intercambiará ambos elementos, y luego pasará a comparar el segundo y el tercer elemento, y así sucesivamente.
Si tenemos total n elementos, luego debemos repetir este proceso n-1 veces.
Se conoce como clasificación de burbujas, porque con cada iteración completa, el elemento más grande en la matriz dada, burbujea hacia el último lugar o el índice más alto, al igual que una burbuja de agua sube a la superficie del agua.
La clasificación se lleva a cabo recorriendo todos los los elementos uno por uno y compararlo con el elemento adyacente e intercambiarlos si es necesario.
NOTA: Si no está familiarizado con la clasificación en la estructura de datos, debe fi Primero aprenda lo que es la clasificación para saber sobre los conceptos básicos de la clasificación.
Implementación del algoritmo de clasificación de burbujas
Los siguientes son los pasos involucrados en la clasificación de burbujas (para clasificar una matriz dada en orden ascendente):
- Comenzando con el primer elemento (índice = 0), compare el elemento actual con el siguiente elemento de la matriz.
- Si el elemento actual es mayor que el siguiente elemento de la matriz, cámbielos.
- Si el elemento actual es menor que el siguiente elemento, muévase al siguiente elemento. Repita el paso 1.
Consideremos una matriz con valores {5, 1, 6, 2, 4, 3}
A continuación, tenemos una representación gráfica de cómo la clasificación de burbujas clasificará la matriz dada.
Entonces, como podemos ver en la representación anterior, después de la primera iteración, 6 se coloca en el último índice, que es la posición correcta para él.
De manera similar, después de la segunda iteración, 5 estará en el penúltimo índice, y así sucesivamente.
Hora de escribir el código para la clasificación de burbujas:
Aunque la lógica anterior clasificará una matriz sin clasificar, el algoritmo anterior no es eficiente porque, según la lógica anterior, el for bucle seguirá ejecutándose durante 6 iteraciones incluso si la matriz se ordena después de la segunda iteración.
Por lo tanto, podemos optimizar claramente nuestro algoritmo.
Algoritmo de clasificación de burbujas optimizado
Para optimizar nuestro bubb le sort algoritmo, podemos introducir un flag para monitorear si los elementos se intercambian dentro del bucle for interno.
Por lo tanto, en el ciclo interno for, verificamos si el intercambio de elementos se está realizando o no, cada vez.
Si para una iteración en particular, no se realizó ningún intercambio lugar, significa que la matriz ha sido ordenada y podemos saltar fuera del ciclo for, en lugar de ejecutar todas las iteraciones.
Consideremos una matriz con valores {11, 17, 18, 26, 23}
A continuación, tenemos una representación gráfica de cómo la clasificación de burbujas optimizada clasificará la matriz dada.
Como podemos ver, en la primera iteración, se realizó el intercambio, por lo que actualizamos nuestro valor flag a 1, como resultado, la ejecución ingresa nuevamente al bucle for. Pero en la segunda iteración, no se producirá ningún intercambio, por lo que el valor de flag permanecerá 0 y la ejecución saldrá del ciclo.
En el código anterior, en la función bubbleSort, si para un ciclo completo único de j iteración (bucle for interno), no se realiza ningún intercambio, luego flag permanecerá 0 y luego saldremos de los for bucles, porque la matriz ya ha sido ordenada.
Análisis de complejidad de la clasificación de burbujas
En la clasificación de burbujas, n-1 se realizarán comparaciones en el primer paso, n-2 en la segunda pasada, n-3 en la tercera pasada y así sucesivamente. Entonces, el número total de comparaciones será,
(n-1) + (n-2) + (n-3) + ….. + 3 + 2 + 1Sum = n (n- 1) /2i.e O (n2)
Por lo tanto, la complejidad temporal de Bubble Sort es O (n2).
La principal ventaja de Bubble Sort es la simplicidad del algoritmo.
La complejidad del espacio para Bubble Sort es O (1), porque solo se requiere un único espacio de memoria adicional, es decir, para la variable temp.
Además, el mejor caso de complejidad de tiempo será O (n), es cuando la lista ya está ordenada.
A continuación se muestra la complejidad de tiempo y espacio para el algoritmo de clasificación de burbujas.
Ahora que hemos aprendido el algoritmo de clasificación de burbujas, también puede consultar estos algoritmos de clasificación y sus aplicaciones:
- Ordenar por inserción
- Ordenar por selección
- Orden rápido
- combinar Ordenar
- Ordenar montón
- Ordenar contando
