Respuestas
Respuesta:
Análisis
Ejemplo del ordenamiento de burbuja ordenando una lista de números aleatorios.
Rendimiento del algoritmo
Artículo principal: Cota ajustada asintótica
Al algoritmo de la burbuja, para ordenar un arreglo de n términos, tiene que realizar siempre el mismo número de comparaciones:
{\displaystyle c(n)={\cfrac {n^{2}-n}{2}}}{\displaystyle c(n)={\cfrac {n^{2}-n}{2}}}
Esto es, el número de comparaciones c(n) no depende del orden de los términos, si no del número de términos:
{\displaystyle \Theta (c(n))=n^{2}\;}{\displaystyle \Theta (c(n))=n^{2}\;}
Por lo tanto la cota ajustada asintótica del número de comparaciones pertenece al orden de n cuadrado.
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:
{\displaystyle \Theta (i(n))=?\;}{\displaystyle \Theta (i(n))=?\;}
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.
Rendimiento en el caso desfavorable
Artículo principal: Cota superior asintótica
Si pasamos al algoritmo un arreglo ordenado en orden inverso realizará un número de comparaciones:
{\displaystyle c(n)={\cfrac {n^{2}-n}{2}}}{\displaystyle c(n)={\cfrac {n^{2}-n}{2}}}
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.
{\displaystyle i(n)={\cfrac {n^{2}-n}{2}}}{\displaystyle i(n)={\cfrac {n^{2}-n}{2}}}
Por lo tanto en el caso más desfavorable tanto el número de comparaciones como el de intercambios coinciden:
{\displaystyle O(c(n))=O(i(n))=n^{2}\;}{\displaystyle O(c(n))=O(i(n))=n^{2}\;}
El número de comparaciones o de intercambios en el caso más desfavorable pertenece al orden de n cuadrado.
Rendimiento en casos óptimos
Artículo principal: Cota inferior asintótica
En el caso óptimo, el más favorable, es la ordenación de un arreglo ya ordenado. En este caso el número de comparaciones será el mismo que en cualquier otro caso:
{\displaystyle \Omega (c(n))=n^{2}\;}{\displaystyle \Omega (c(n))=n^{2}\;}
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:
{\displaystyle i(n)=0\;}{\displaystyle i(n)=0\;}
Por lo tanto el coste de intercambios no depende de n, y es constante:
{\displaystyle \Omega (i(n))=1\;}{\displaystyle \Omega (i(n))=1\;}
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. Esto lo cataloga como uno de los algoritmos de ordenación más ineficientes que existen, aunque para muchos programadores sea el más sencillo de implementar
Explicación:
Algoritmo de ordenamiento. Burbuja(Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. 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. ... También es conocido como el método del intercambio directo.