Método de Ordenamiento Burbuja

  • Published on
    04-Nov-2015

  • View
    24

  • Download
    0

DESCRIPTION

burbujaaa

Transcript

<p>Explicacin del algoritmo:</p> <p>Estealgoritmoobtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeas "burbujas". La idea bsica del ordenamiento de la burbuja es recorrer el conjunto de elementos en forma secuencial varias veces. Cada paso compara un elemento del conjunto con su sucesor(x[i] con x[i+i]), e intercambia los dos elementos si no estn en el orden adecuado. El algoritmo utiliza una bandera que cambia cuando se realiza algn intercambio de valores, y permanece intacta cuando no se intercambia ningn valor, pudiendo as detener el ciclo y terminar el proceso de ordenamiento cuando no se realicen intercambios, lo que indica que este ya est ordenado. Este algoritmo es de fcil comprensin y programacin pero es poco eficiente puesto que existenn-1pasos yn-icomprobaciones en cada paso, aunque es mejor que el algoritmo de ordenamiento por intercambio.</p> <p>Explicacin de Complejidad:La complejidad del algoritmo de la burbuja es O(n) en el mejor de los casos y O(n) en el peor de los casos, siendo su complejidad total O(n).</p> <p>Conclusiones:Este algoritmo funciona de forma parecida al de Seleccin, pero haciendo ms trabajo para llevar cada elemento a su posicin. De hecho es el peor con respecto a los ordenamientos por seleccin e insercin , no slo en cuanto al tiempo de ejecucin, sino tambin respecto al nmero de comparaciones y de intercambios que realiza. Una posible mejora que puede admitir este algoritmo es el control de la existencia de una pasada sin intercambios; en ese momento el vector estar ordenado. </p>