Tarea Viernes 1/07/11 ( Algoritmo Simple)

Algoritmo Simple: 
Ordenacion por metodo de burbuja

El metodo burbuja consiste en ordenar de manera secuencial una cadena de caracteres al ir remplazando los caracteres dependiendo de su valor en la cadena.

Este algoritmo es muy sencillo por lo cual lo considere para mi ejemplo:
Diagrama

Programa
void ordenamientoBurbuja(int v[], int util_v) { int temp, i, j; for (i = 0; i < util_v -1 ; i++) { for (j = i + 1; j < util_v ; j++) { if (v[i] > v[j]) { temp = v[i]; v[i] = v[j]; v[j] = temp; } } }}
Como visto en :
http://es.wikipedia.org/wiki/Ordenamiento_de_burbuja 

Rendimiento del Algoritmo

Rendimiento del algoritmo
Para poder ordenar satisfactoriamente tenemos que usar el mismo numero 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 numero 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 el vector 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.
[editar]Rendimiento en el caso desfavorable
Artículo principal: Cota superior asintótica

Si pasamos al algoritmo un vector ordenado en orden inverso realizara un numero 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 realizara el intercambio.
Por lo tanto en el caso más desfavorable tanto el numero de comparaciones como el de intercambios coinciden:

El numero 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 optimo, 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 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. Esto lo cataloga como el algoritmo mas ineficiente que existe, aunque para muchos programadores sea el más sencillo de implementar.

Bibliografia:

http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/anasin.pdf
http://es.wikipedia.org/wiki/Ordenamiento_de_burbuja

http://www.estructuradedatos.galeon.com/burbujatext.htm