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.
Gracias por el aporte :3