2

Ordenamiento burbuja

El ordenamiento burbuja

El ordenamiento burbuja hace múltiples pasadas a lo largo de una lista. Compara los ítems adyacentes e intercambia los que no están en orden. Cada pasada a lo largo de la lista ubica el siguiente valor más grande en su lugar apropiado. En esencia, cada ítem “burbujea” hasta el lugar al que pertenece.
En la siguiente figura se observa la primera pasada de un ordenamiento burbuja. Los ítems sombreados se comparan para ver si no están en orden. Si hay n ítems en la lista, entonces hay n-1 parejas de ítems que deben compararse en la primera pasada. Es importante tener en cuenta que, una vez que el valor más grande de la lista es parte de una pareja, éste avanzará continuamente hasta que la pasada se complete.

Al comienzo de la segunda pasada, el valor más grande ya está en su lugar. Quedan n−1 ítems por ordenar, lo que significa que habrá n−2 parejas. Puesto que cada pasada ubica al siguiente valor mayor en su lugar, el número total de pasadas necesarias será n−1. Después de completar la pasada n−1, el ítem más pequeño debe estar en la posición correcta sin requerir procesamiento adicional.

El siguiente codigo muestra la función ordenamientoBurbuja completa. La función recibe la lista como un parámetro, y lo modifica intercambiando ítems según sea necesario.

defordenamientoBurbuja(unaLista):for numPasada in range(len(unaLista)-1,0,-1):
        for i in range(numPasada):
            if unaLista[i]>unaLista[i+1]:
                temp = unaLista[i]
                unaLista[i] = unaLista[i+1]
                unaLista[i+1] = temp

unaLista = [54,26,93,17,77,31,44,55,20]
ordenamientoBurbuja(unaLista)
print(unaLista)

Para analizar el ordenamiento burbuja, debemos tener en cuenta que independientemente de cómo están dispuestos los ítems en la lista inicial, se harán n−1 pasadas para ordenar una lista de tamaño n.
El número total de comparaciones es la suma de los primeros n−1 enteros. Recuerde que la suma de los primeros n números enteros es (1/2)n^2+(1/2)n. La suma de los primeros n-1 enteros es (1/2)(n^2)+(1/2)(n)-n, que es igual a (1/2)n^2−(1/2)n. Esto es todavía O(n^2) comparaciones . En el mejor de los casos, si la lista ya está ordenada, no se realizarán intercambios. Sin embargo, en el peor de los casos, cada comparación causará un intercambio. En promedio, intercambiamos la mitad de las veces.

Un ordenamiento burbuja se considera frecuentemente como el método de ordenamiento más ineficiente ya que debe intercambiar ítems antes de que se conozca su ubicación final. Estas operaciones de intercambio “desperdiciadas” son muy costosas. Sin embargo, debido a que el ordenamiento burbuja hace pasadas por toda la parte no ordenada de la lista, tiene la capacidad de hacer algo que la mayoría de los algoritmos de ordenamiento no pueden. En particular, si durante una pasada no hubo intercambios, entonces sabemos que la lista ya debe estar ordenada.

Un ordenamiento burbuja se puede modificar para detenerse anticipadamente si encuentra que la lista ya ha sido ordenada

Escribe tu comentario
+ 2
0
11838Puntos

Gracias por el aporte :3