Ordenamiento burbuja

Comparación de ordenamiento burbuja con le quicksort
La Ordenación de burbuja (BubbleSort 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. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cualsignifica 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". También es conocido como el método del intercambio directo.
Rendimiento del algoritmo
Artículo principal: Cota ajustada asintótica.
Al algoritmo de la burbuja, para ordenar un vector de n términos, tiene querealizar siempre el mismo número de comparaciones:

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.

Por lo tanto la cota ajustada asintótica del número de comparaciones pertenece al orden de n cuadrado.
El numero de intercambios i(n), que hay que realizar depende del orden de los términos y podemos diferencia, el caso mejor, si elvector esta previamente ordenado, y el caso peor, si el vector esta ordenado en orden inverso.

por lo que no se puede determinar una cota ajustada asintótica del número de intercambios, dado que este dependerá del orden del vector en cuestión.
Rendimiento en el caso desfavorable
Artículo principal: Cota superior asintótica.
Si pasamos al algoritmo un vector ordenado en orden inverso realizaraun número de comparaciones:

Como ya hemos dicho anteriormente, y tendrá que realizar un número igual de intercambios entre los términos del vector, dado que en cada comparación los términos estarán desordenados, y se realizará el intercambio.

Por lo tanto en el caso más desfavorable tanto el número de comparaciones como el de intercambios coinciden:

El número de comparaciones o deintercambios 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 que un vector ya ordenado, 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 ncuadrado, 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 lalista 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 el algoritmo mas ineficiente que existe, aunque para muchos programadores sea el más sencillo de implementar.
El ordenamientorápido (quicksort en inglés) es un algoritmo creado por el científico británico en computación C. A. R. Hoare basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
El ordenamiento rápido (quicksort en inglés) es un algoritmo creado por el científico británico en computación C. A. R. Hoare basado en la técnica de divide yvencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
En conclusión, el número total de comparaciones que hace el algoritmo es:
, donde, por tanto el tiempo de ejecución del algoritmo en el mejor caso es.

ANALISIS DE EFICIENCIA DEL METODO DE QUICKSORT
Diversos estudios realizados sobre el comportamiento del mismo demuestran que si se escoge en cada pasada...