Ordenamiento de burbuja

Agregué un contador en el algoritmo para ver cuántos pasos le tomaba realmente. Después lo convertí en una gráfica en desmos.com 🤘

El resultado fue una parábola, lo que significa que es una función cuadrática: O(n**2). Sólo se ve la mitad de la parábola porque el input siempre va a ser positivo en este caso. 😎

Me gustaría agregar, si es que no lo hicieron ya, que la lista se está pasando como referencia, por lo que la lista original es ordenada ordena y no hay necesitad de hacer un return de esta.

Trate de hacer el algoritmo antes de ver como lo hacía el profesor, afortunadamente lo logre, eso si me tarde algo, para ello hice un ejercicio manual de como se tendría que comportar y me di cuenta de una cosa, y es que la lista en cada iteración se va acortando cosa que reulta muy curiosa, si nos fijamos en su forma.

Esta forma es la de un Triangulo

Entonces uno podría pensar que la complejidad es igual a la formula del triangulo, donde la base y la altura valen lo mismo o sea n veces.

Pero probando esto no es del todo verdad por teoricamente se obtendria lo siguiente

Con una lista de 7 elementos se tendria 77/2 = 24.5, pero en practica es 21
con 8 se tendría 88/2 = 32, pero en practica es 28
con 9 se tendría 9*9/2 = 40.5, pero en practica es 36

Haciendo análisis veo que la complejidad exacta es O(n*n/2) - O(n/2)

En conclusión es interesante encontrar coincidencias cuando se trata de matemáticas

DEJO MI CÓDIGO

import random

def ordenamiento_burbuja(lista, tamano_de_la_lista):
    step = 0
    for posicion in range(tamano_de_la_lista):
        for j in range(0, tamano_de_la_lista - posicion - 1):
            print(j)
            if lista[j] > lista[j + 1]:
                value = lista[j]
                lista[j] =  lista[j + 1]
                lista[j + 1] = value
            step += 1
        print(lista)

    return (lista, step)

            
# (n*n)/2 - n/2
# 36, 28, 21

if __name__ == '__main__':
    tamano_de_la_lista = int(input('De que tamano sera la lista a la que quiere buscar: '))
    lista = [random.randint(0, 100) for i in range(tamano_de_la_lista)]

    (lista_ordenada, step)  = ordenamiento_burbuja(lista, len(lista))

    print(lista_ordenada)
    print(step)

Me saqué las ganas de poner para que imprima paso por paso cómo avanza la burbuja:

import random


def ordenamiento_burbuja(lista):
    n = len(lista)

    for i in range(n):
        for j in range(0, n - i - 1):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                print(lista) # Este detalle es para ver todo el recorrido de la lista ordenando los números 
                     
    return lista
    
if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamano es la lista? '))

    lista = [random.randint(0, 100) for i in range(tamano_de_lista)]
    print(lista)

    lista_ordenada = ordenamiento_burbuja(lista)
    print(lista_ordenada)

Bueno me he tirado toda la tarde probando lo que decia y comprobando el tiempo como se hablaba en otras clases el tiempo que tarda es casi la mitad

Para ordenar 5.000 elementos
9.865180492401123 Buble
5.607348442077637 Buble_propio

Para ordenar 10.000 elementos
15.066108465194702 Buble
7.076613903045654 Buble_propio

a mi me esta costando, pero practico y practico con la terminal CMD para probar cada función y así le estoy entendiendo. definitivamente ser profesor de matemáticas me ayudo bastante para entender.

Les dejo la implementacion en C++:

#include <iostream>
#include <vector>
#include <time.h>


std::vector<int> ordenamientoBurbuja(std::vector<int> v);


int tam=0;

std::vector<int> v;
int main(int argc, char **argv){
	srand(time(NULL));
	std::cout<<"Enter tam of list"<<std::endl;
	std::cin>>tam;
	std::cout<<"Vector desordenado: "<<std::endl;
	for(int  i=0; i<tam; i++){
		v.push_back(rand()%101);
		std::cout<<v[i]<<" ";
	}
	std::vector<int> vOrdenado = ordenamientoBurbuja(v);
	std::cout<<"\nVector Ordenado: "<<std::endl;
	for(auto v : vOrdenado){
		std::cout<<v<<" ";
	}
	return EXIT_SUCCESS;
}
std::vector<int> ordenamientoBurbuja(std::vector<int> v){
	for(int i=0; i<v.size()-1; i++){
		for(int j=0; j<v.size()-i-1; j++){
			if(v[j]>v[j+1]){
				auto temp = v[j];
				v[j]=v[j+1];
				v[j+1]= temp;
			};
		}
	}
	return v;
}

Llevo bastantes años de carrera en el mundo de TI, pero qué agradable hubiese sido si mi profesor de universidad me hubiese explicado así todo esto. Gran explicación y ejemplo 😃

Punto para Platzi por este tipo de explicaciones gráficas. Esto se podría implementar en casi todos los temas y en casi todos lo cursos.

Hay un error en la explicación del profesor, lo digo solo para aclarar y es que con este algoritmo después de la primera ronda el numero mayor no quedara de ultimo.
Aquí el output del algoritmo con algunas adiciones demostrando mi punto:

Aqui el código:

Espero que sea de utilidad.

Que placer programar con Python!
Swapping en Python 🐍 :

Swapping en Java ☕️:

Definitivamente la forma que implementa es muy buena. Yo intenté hacer el algoritmo por mi cuenta y en términos de tiempo, el que está en el curso es mejor.

import random, time

def ordenamiento_burbuja(lista):
    cuenta=0
    while cuenta!=len(lista)-1:
        cuenta=0
        for i in range(1,len(lista)):
            if lista[i-1]>lista[i]:
                lista[i],lista[i-1]=lista[i-1],lista[i]
            else:
                cuenta+=1
    return lista

def ordenamiento_de_burbuja(lista):
    n = len(lista)

    for i in range(n):
        for j in range(0, n - i - 1): # O(n) * O(n) = O(n * n) = O(n**2)

            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]

    return lista


if __name__=='__main__':

    lista=[random.randint(0,100) for i in range(10000)]


    lista_1=lista
    lista_2=lista

    comienzo=time.time()
    ordenamiento_burbuja(lista_1)
    final=time.time()
    print(final-comienzo)
    
    comienzo=time.time()
    ordenamiento_de_burbuja(lista_2)
    final=time.time()
    print(final-comienzo)

es un algoritmo bastante sencillo de aprender, pero aqui en python feu mas facil programarlo, o por lo menos asi lo senti, corto y facil de hacer

Los algoritmos que sacamos de estas clases es brutal, algo que es tan fácilmente, viendo estos ejemplos, entendemos que nuestra manera de pensar es lo que hace todo en la programación.

.

Ordenamiento de burbuja.

• También conocido como Bubble Sort. Es un algoritmo que recorre repetidamente una lista que necesita ordenarse. Compara elementos adyacentes y los intercambia si están en el orden correcto. Este procedimiento se repite hasta que no se requieren más intercambios, lo que indica que la lista se encuentra ordenada.
• Tenemos garantizado encontrar el mas pequeño o el mas grande (dependiendo de nuestro orden) en un solo paso, esto es, en $O(n)$.
• La complejidad algorítmica es en el peor de los casos $O(n^2)$.

import random
import matplotlib.pyplot as plt
import seaborn as sns

sns.set_theme()

def burbuja(ordena):
    iteracion = 0
    N = len(ordena) -1
    
    for i in range(N):
        for j in range(0, N-i):
            if ordena[j] > ordena[j+1]:
                ordena[j], ordena[j+1] = ordena[j+1] , ordena[j]
            iteracion += 1       
    return ordena, iteracion
                
if __name__ == '__main__':
    
    x = [5+2*x for x in range(50)]
    iteracion = []
    
    for n in x:
    
        lista = [random.randint(0, 100) for i in range(n)]
        lista_ordenada, aux = burbuja(lista.copy())
        iteracion.append(aux)
        
    plt.plot(x, iteracion)

Complejidad Algoritmica Ordenamiento de burbuja

Aquí en este video de Youtube se pueden ver varios algoritmos de ordenamiento. Son animaciones bastante intuitivas de cómo funciona cada uno.
https://www.youtube.com/watch?v=kPRA0W1kECg

Un dato curioso, dado que la función recibe una lista, normalmente estos objetos son tratados por “referencia”, es decir se modifica la lista misma, por lo cual no es necesario retornar la lista ordenada, va un ejemplo:

import random

def bubleeSort(l: list):
    n = len(l)
    for i in range(n):
        ordered = True
        for j in range(0, n - i - 1):
            if l[j] > l[j+1]:
                l[j], l[j+1] = l[j+1], l[j]
                ordered = False
        if ordered: break
                

if __name__ == '__main__':
    n = int(input('N: '))
    l = [random.randint(0, 100) for i in range(n)]
    print(l)
    bubleeSort(l)
    print(l)

Al ejecutarlo imprime:

N: 20
>>> [73, 2, 86, 9, 5, 96, 77, 11, 16, 3, 64, 76, 67, 67, 59, 100, 3, 55, 9, 28]
>>> [2, 3, 3, 5, 9, 9, 11, 16, 28, 55, 59, 64, 67, 67, 73, 76, 77, 86, 96, 100]

Si quiere ver mejor lo que ocurre dentro del ordenamiento de la burbuja, correr este codigo:

import random

def  ordenamiento_de_burbuja(lista):
    print(f'Lista Original: {lista}\n')
    n = len(lista)
    vuelta = 0
    
    for i in range(n):
        vuelta += 1
        print(f'Esta es la vuelta: {vuelta}')
              
        for j in range(0, n - i - 1):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
              
        print(f'La lista esta quedando asi {lista}\n')

if __name__ == '__main__':
    tamaño_de_lista = int(input('De que tamaño sera la lista: '))
    objetivo = int(input('Que numero quieres encontrar: '))
    
    lista = [random.randint(0, 100) for i in range(tamaño_de_lista)]
    
    encontrado = ordenamiento_de_burbuja(lista)
    
    # print(lista)
    # print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
    
    ############# Ordenamiento de Burbuja.

Pensando en el ordenamiento y como funcionan todo, no seria mucho mejor buscar el elemento mayor y menor en cada vuelta del loop y asignarlo a la primera y ultima posicion?

1. Tenemos un array con elementos desordenados, el cual le medimos la longitud y la asignamos a una varaible llamada n.
2. Creamos el primer bucle i, este se basara en ser un bucle externo que ejecutara todas las veces que sea necesario el bucle interno.
3. creamos el bucle interno, este bucle utilizara la variable j. Este recorrera el array y comparara el elemento j y j + 1, al final cuando termine este primer bucle, habremos conseguido en el final del array el elemento mas grande. Pero este bucle tiene algo muy peculiar, que es el (0, n - i -1) De que trata esto? Sencillo, se basa en que SIEMPRE empezaremos en la posicion 0, pero cada vez que i, itere… iremos poniendo atras de todo en el array, los elementos mas grandes, por lo tanto, en la primer iteracion, con i = 0 dejaremos al elemento mas grande atras de todo el array, pero… ya en la segunda iteracion con i = 1, no nos interesa comparar el ultimo elemento del array, ya que este ya sabemos que es el mas grande de todos, por lo tanto, conseguiremos al segundo mas grande y este se posicionara en el ante ultimo lugar del array, como se consigue eso? n - 1 -1 y por que siempre hay un -1 al final? bueno, eso es mas facil, eso lo debemos hacer, ya que estamos jugando con elementos basados en n, y n es la longitud del array, n = 8, pero resulta que al jugar con posiciones, nosotros siempre empezamos de 1, entonces son 8 posiciones, pero para acceder a la posicion numero 8, esta es n[7], porque siempre empezamos en 0!

if lista[j] > lista[j + 1]:
                
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista

y esto simplemente se basa en la asignacion y comparacion de el elemento 0, con el 1, el 1 con 2, el 2 con el 3. Lo unico curioso es que la sintaxis esta solo suce en python por lo tanto, si quiero hacerlo en js, debo ver en youtube como se escribe esta partesita.

Aquí va mi código, creo que la notación sería O(n) ya que el inicio del while no depende de n(lista), mientras que el for sí depende de n(lista), si me equivoco agradecería que me corrigieran, saludos

import random

def bubble(lista):
    while True:
        for i in range(len(lista)-1):
        
            if lista[i] > lista[i+1]:
                lista[i], lista[i+1] = lista[i+1], lista[i]
        
        if sorted(lista) == lista[:]:
            return lista[:]
            break

if __name__ == "__main__":

    lista = [random.randint(0,100) for i in range(10)]
    # lista = [1,5,6,8,4,1,2,6,7,8,9,6,5,123,21,421,12,42,31,21,0,9,8]
    print(lista)
    print("-----------------------------------")
    print(bubble(lista))

Les dejo mi bubble sort, me parece que al profesor le faltó poner el caso donde el elemento actual de la lista es igual al siguiente

def bubble(lista):

    n = len(lista)
    
    for i in range(n):
        for j in range(0, n - i - 1):
            if lista[j] > lista [j + 1]:
                lista[j], lista[j + 1] = lista[j+1], lista[j] #Swap
            if lista[j] == lista[j + 1]:
                pass
    return lista

por que no funciona mi codigo?

import random

def ordenamiento_de_burbuja(lista):
    n = len(lista)
    
    for i in range(n):
        for j in range(0, n - i - 1):
            
            if lista[(j)] > lista[(j + 1)]:
                lista[(j)], lista[(j + 1)] = lista[(j + 1)], lista[(j)]
            
    return lista       
            
if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamano sera la lista? '))
   
#Funcion sorted ordena la lista

    lista = [(random.randint[0, 100] for i in range(tamano_de_lista))]

    print(lista)
    
    lista_ordenada = ordenamiento_de_burbuja(lista)
    print(lista_ordenada)```

En este algoritmo la cantidad de pasos se reduce linealmente con el recorrido sobre la lista:
La evaluación del 1° elemento recorre hasta len(lista)-1
La evaluación del 2° elemento recorre hasta len(lista)-2
.
…
La evaluación del. i-esimo elemento recorre hasta len(lista)-i

import random
def buble_sort(lista):
i=1
j=0
for scan0 in range(len(lista)-i):
for scan in range(len(lista)-i):
j += 1
a = lista[scan]
b = lista[scan+1]

        if a > b:
            lista[scan]   = b
            lista[scan+1] = a
            #print(scan,a,b)
    i+=1
print(f'#pasos {j}')

if name == ‘main’:
lista = [random.randint(0, 1000) for i in range(20)]
#lista[0] = 100
print (lista)
buble_sort(lista)
print (lista)

por qué en el primer for no es
for i in range(n-1)
no haría esto más eficiente el código ?

Cómo dato curtioso esto es lo que se ve en al caja negra en esta parte for j in range(0, n - i - 1):

[34, 47, 20, 45, 24, 52, 35, 0, 71, 100]
iteracion i 0
iteracion j 0
iteracion j 1
iteracion j 2
iteracion j 3
iteracion j 4
iteracion j 5
iteracion j 6
iteracion j 7
iteracion j 8
iteracion i 1
iteracion j 0
iteracion j 1
iteracion j 2
iteracion j 3
iteracion j 4
iteracion j 5
iteracion j 6
iteracion j 7
iteracion i 2
iteracion j 0
iteracion j 1
iteracion j 2
iteracion j 3
iteracion j 4
iteracion j 5
iteracion j 6
iteracion i 3
iteracion j 0
iteracion j 1
iteracion j 2
iteracion j 3
iteracion j 4
iteracion j 5
iteracion i 4
iteracion j 0
iteracion j 1
iteracion j 2
iteracion j 3
iteracion j 4
iteracion i 5
iteracion j 0
iteracion j 1
iteracion j 2
iteracion j 3
iteracion i 6
iteracion j 0
iteracion j 1
iteracion j 2
iteracion i 7
iteracion j 0
iteracion j 1
iteracion i 8
iteracion j 0
iteracion i 9
[0, 20, 24, 34, 35, 45, 47, 52, 71, 100]

Caracteristica de burble sort, después de la primera ronda, el elemento más grande esta al final

Buenas tardes.
Se podría sacar una vualta al primer for:
"for i in range(n-1):"
Por ejemplo si tuviera una lista de n=2. Sólo necesitaría recorrerla i=1 vez, y no i=2 veces.
Slds

¡Excelente clase!

## Ordenamiento de burbuja (Bubble sort)
El primer algoritmo de ordenamiento que veremos es el ordenamiento de burbuja. Es un algoritmo que recorre repetidamente una lista que necesita ordenarse. Compara elementos adyacentes y los intercambia si están en el orden incorrecto. Este procedimiento se repite hasta que no se requiere mas intercambios, lo que indica que la lista se encuentra ordenada.

Este algoritmo tiene una complejidad de O(n^2)

def ordenamiento_de_burbuja(lista):
    n = len(lista)

    for i in range(n):
        for j in range(0, n - i - 1):
            if lista[j] > lista[j - 1]:
                # Notacion para hacer swapping 😱
                lista[j], lista[j + 1] = lista[j + 1], lista[j]

    return lista

antes de ver la clase trate de crear mi propio algoritmo, en el que use recursividad el output es el mismo una lista ordenada de menor a mayor

``
    for i in range(n):
        for j in range(0, n - i - 1): # O(n^2)
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista
```

El algoritmo de ordenamiento de burbuja es un algoritmo de ordenamiento simple pero ineficiente. Funciona comparando repetidamente elementos adyacentes en una lista y cambiándolos de posición si están en el orden incorrecto. Este proceso se repite hasta que no se requieren más intercambios, lo que indica que la lista está ordenada. Aquí tienes una descripción del algoritmo de ordenamiento de burbuja:

Ordenamiento de Burbuja:

• Descripción: El algoritmo de ordenamiento de burbuja compara elementos adyacentes en la lista y los intercambia si están en el orden incorrecto. Comienza desde el inicio de la lista y compara el primer elemento con el segundo. Si el primer elemento es mayor que el segundo, se intercambian. Luego, se pasa al siguiente par de elementos y se repite el proceso. Este proceso continúa hasta que se llega al final de la lista.
• Utilidad: El ordenamiento de burbuja es un algoritmo de ordenamiento simple y comprensible, pero es muy ineficiente en términos de tiempo de ejecución. Se utiliza principalmente con fines educativos para enseñar los conceptos de ordenamiento y no es adecuado para listas de gran tamaño.
• Complejidad Temporal: La complejidad temporal en el peor caso del ordenamiento de burbuja es O(n^2), donde “n” es el número de elementos en la lista. Esto significa que el tiempo de ejecución aumenta cuadráticamente con el tamaño de la lista, lo que lo hace ineficiente para listas grandes.

Que hermosa clase:

el flag ayuda a reducir las iteraciones, pero por supuesto sigue siendo n**2

• En este algoritmo de ordenamiento de una lista. tomamos los dos primeros indices y nos fijamos si el primer indice es mayor que el segundo, si es asi, intercambiamos el primer indice por el segundo, de lo contrario, si el primer indice nos es mayor que el segundo no hacemos nada, ya que significa que estan ordenados estos dos indices.
• Hacemos ese proceso recorriendo la lista varias veces. Cuantas veces iteramos la lista?, hasta que ya no haiga ningun primer indice mayor que el segundo (osea que ya este todo ordenado). Este algoritmo asegura que desde la primera iteracion se ordene el numero mayor hasta el final.
  .

def ordenamiento_de_burbuja(lista):
    n = len(lista)
    for i in range(n):
        for j in range(0, n - i - 1): # O(n) * O(n) = O(n * n) = O(n**2)
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista

if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamano sera la lista? '))
    lista = [random.randint(0, 100) for i in range(tamano_de_lista)]
    print(lista)
    lista_ordenada = ordenamiento_de_burbuja(lista)
    print(lista_ordenada)

.
Este algoritmo no es muy eficaz con una gran cantidad de datos, puede tardar minutos o inlcuso horas, ya que es un algoritmo cuadratico. Y te puede tardar demasiado tiempo con una compu no muy grata en componentes como la mia:

Mi cimpu con 8 de ram y un intel aceleron con el ordenameinto de burbuja de 1,000,000 de numeros

En esta clase se presentó el algoritmo de ordenamiento de burbuja, el cual funciona comparando elementos adyacentes y los intercambia si están en el orden incorrecto. Se explicó la complejidad algorítmica y el uso de la notación Big O para describirla en términos asintóticos. También se discutió sobre los recorridos lineales y dobles de una lista, y se mencionaron otros algoritmos de ordenación como Inserción Sort y Quick Sort.

Recuerda que la complejidad algorítmica es una medida de la cantidad de recursos necesarios para resolver un problema, y es importante elegir el algoritmo adecuado para el tamaño de la lista que se quiere ordenar.

Sí la **primera y segunda listas están ordenadas ** es porque algo paso ¿no?
En mi caso copié y pegue el código de la clase anterior y en la anterior tiene puesto el método sorted() que ya ordena la lista, es decir, se crea la lista, el método la ordena y después se le pasa a la variable lista (se le pasa ordenada), ordenar algo ordenado, no es gracias, así que para solucionarlo, solo saqué el método sorted() del inicio y listo.
Espero les sirva sí tenían el mismo error que yo

import random

def ordenamiento_de_burbuja(lista):
    n = len(lista)

    for i in range(n):
        for j in range(0, n - i - 1):

            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista

if __name__ =='__main__':
    tamaño_de_lista = int(input("De que tamaño sera la lista?"))
   

    lista = [random.randint(0, 100) for i in range(tamaño_de_lista)]
    print(lista)

    lista_ordenada = ordenamiento_de_burbuja(lista)
    print(lista_ordenada)

¡Qué buena Diapositiva! En la Universidad explicaron esto de una forma compleja, pero resultó ser muy sencillo 😅 me gustaría tener acceso a esa diapositiva o al menos al gif que lo muestra paso a paso

según lo que se ve no es necesario que el ordenamiento burbuja sea n**n sino n!

las comparaciones

En esta página pueden visualizar de una manera muy similar a la que presento el profesor los algoritmos de ordenamiento y además se puede visualizar el código como si estuvieran haciendo debugging:
https://visualgo.net/en/sorting?slide=1

• Después de cada pasada (el bucle for más externo), el elemento de más valor se ubica en el extremo del arreglo. Lo que significa que toma su posición correcta, por este motivo sería conveniente que en vez de realizar todas las comparaciones en la segunda pasada, se haga una comparación menos. Para esto usamos una variable comparaciones la cual cada vez que se complete un ciclo for externo (una pasada), se decrementa en 1 mediante la instruccion comparaciones

def pedirDatos():
    lista=[]
    while True:
        n=int(input("Humano ingres el numero que quieras (0 para terminar):"))
        if n==0:
            return lista
        else:
            lista.append(n)
    return lista

def burbuja(lista):
    cont=0
    ordenado=False
    tamano=len(lista)
    comparaciones=tamano
    for _ in range(0,tamano):
        if ordenado==True:
            break
        for j in range(0,comparaciones-1):
            ordenado=True
            cont=cont+1
            if lista[j]>lista[j+1]:
                ordenado=False
                aux=lista[j]
                lista[j]=lista[j+1]
                lista[j+1]=aux
        comparaciones=comparaciones-1
    return lista,cont
def mostrarLista(lista,cont):
    tam=len(lista)
    print(f"Humano aqui esta tu piche lista ordenada en {cont} ciclos de forma acendente:")
    for i in range(0,tam):
        print(f"{lista[i]}")
    print(f"Humano aqui esta tu piche lista ordenada en {cont} ciclos de forma desendente:")
    for i in range(tam,0,-1):
        print(f"{lista[i-1]}")

lista=pedirDatos()
lista,cont=burbuja(lista)
mostrarLista(lista,cont)

Intente hacer el algoritmo antes de ver el cómo lo hace el profe, fue de esta forma mi código.

Este algoritmo funciona comparando en el vector dos elementos adyacentes, si el segundo elemento es menor a el primero entonces son intercambiados, en caso contrario se evalua el segundo elemento y el siguiente elemento adyacente a su izquierda.

Una vez terminada la primera iteración se vuelve a realizar el mismo procedimiento sin embargo en cada iteración hecha, un elemento del vector, de derecha a izquierda, ya no es evaluado ya que contiene el número mayor de cada iteración.

El algoritmo terminará una vez que el número de iteraciones sea igual a el numero de elementos que contenga el vector de numeros.

El código en Python:

#Declaración de Funciones
 
def burbuja(A):
    for i in range(1,len(A)):
        for j in range(0,len(A)-i):
            if(A[j+1] < A[j]):
                aux=A[j];
                A[j]=A[j+1];
                A[j+1]=aux;
    print A;
 
#Programa Principal
A=[6,5,3,1,8,7,2,4];
print A
burbuja(A);

Les dejo mi implementación utilizando recursividad

import random


def bubble_sort_algorithm(input_list, limit=0):
    last_change = 0

    if limit == 0:
        limit = len(input_list)

    for i in range(limit - 1):

        if input_list[i] > input_list[i + 1]:
            input_list[i], input_list[i + 1] = input_list[i + 1], input_list[i]
            last_change = i + 1

    return bubble_sort_algorithm(input_list, last_change) if last_change > 0 else None


if __name__ == '__main__':
    list_to_sort = [random.randint(0, 100) for _ in range(100)]

    # Print unsorted list
    print(list_to_sort)

    # Sorting List
    bubble_sort_algorithm(list_to_sort)

    # Print sorted list
    print(list_to_sort)

Creo que más bien la complejidad seria O((n-1)!), debido a que en el peor de los casos se tendrían (n-1)! operaciones, si el arregle tiene un tamaño 8, encontrar el mayor de los elementos haciendo una iteración de BubbleSort tomaría como máximo 7 comparaciones, para la siguiente iteración tomaria 6, etc, por lo tanto la complejidad debería de ser O( (n-1)! )

Este procedimiento se repite hasta que no se requiere mas intercambios, lo que indica que la lista se encuentra ordenada.

El ordenamiento de burbuja. Es un algoritmo que recorre repetidamente una lista que necesita ordenarse. Compara elementos adyacentes y los intercambia si están en el orden incorrecto.

Este algoritmo es un poco (no mucho) mas eficiente pues al momento en que detecta que la lista esta ordenada para el bucle

def ordenarLista(lista) :

    cambio=True
    final=len(lista)-1
    contador = 0

    while(cambio) :
        cambio=False
        for i in range(final) :
            if i != final :
                if lista[i] > lista[i + 1] :
                    bandera = lista[i]
                    lista[i] = lista[i +1]
                    lista[i + 1] = bandera
                    cambio=True
            
            contador+=1
        final-=1

    print(f"Algoritmo #1 tardo en ordenar = {contador} vueltas")
    return lista

Les adjunto mi algoritmo, he pensado en usar un booleano para comprobar si la lista esta ordenada en algún punto de la ejecución y así ahorrar computo, luego devuelvo el número de iteraciones necesarias:

from random import randint

def bubble_sorting(my_list):
    size = len(my_list)
    for i in range(0, size):
        ordered = True #List ordered flag, if we need a swap then it will set to false in the inner loop.
        for j in range(1, size):
            if my_list[j - 1] > my_list[j]: #Swap
                my_list[j - 1], my_list[j] = my_list[j], my_list[j - 1]
                ordered = False
        
        #Now We should check if ordered is True => There is no need to continue ordering
        if ordered == True:    
            iteration_number = i
            break
    return iteration_number


def run():
    size = int(input('Insert list size: '))
    random_list = [randint(1, size) for i in range(1, size)]
    print(f'The original list is: {random_list}')
    iterations = bubble_sorting(random_list)
    print(f'The final list is: {random_list}\n It did need {iterations} iterations')
    

Para complementar https://runestone.academy/runestone/static/pythoned/SortSearch/ElOrdenamientoBurbuja.html

Clases para buenas.

Se trabaja con “len” y a que este devuelve el numero de caracteres en una cadena

cuando dijo que los errores nos pasan a todos me recordo a bob ross

El ordenamiento de burbuja es un algoritmo que recorre repetidamente una lista que necesita ordenarse. Compara elementos adyacentes y los intercambia si están en el orden incorrecto. Este procedimiento se repite hasta que no se requieren más intercambios, lo que indica que la lista se encuentra ordenada.

Después de la primera iteración del ordenamiento de burbuja tenemos la garantía de que el ultimo elemento es el más grande de la lista.

yo veo algo así:

Π (n-i) = (n-0)*(n-1)*(n-2)*.........*(n - (n-1))

siendo n la longitud del algotimo, i_minimo=0, i_maximo= n -1. y el simbolo Π el productorio. Entonces seria algo como el productorio de (n-i) desde i_minimo hasta i_maximo.

Creo que se le está yendo una iteración de más, yo le resté una al for de afuera.

def bubble_sort(my_list):
    size = len(my_list)

    if (size == 0 or size == 1):
        return my_list

    for i in range(size - 1):
        for j in range(size - 1 - i):
            if my_list[j] > my_list[j + 1]:
                my_list[j], my_list[j + 1] = my_list[j + 1], my_list[j]

    return my_list

bubble el sort, no es capaz sobrepasen las 4 cifras.

El crecimiento del bubble sort, es un crecimiento polinomineal .

a la hora de reasignar varias variables en una misma línea, lo llamamos swapping.

Dentro de nuestro algoritmo de bubble sort, podemos hacer que recorra cada iteración un poco menos, para evitar que siempre recorra toda la lista.

Lo interesante del bubble sort, es que después de la primera ronda, tenemos casi que asegurado, que el número más grande se encuentra al final.

El bubble sort, recorre una lista comparando los elementos adyacentes y los intercambia si están en el orden incorrecto. Si la lista está ordenada en su totalidad, entonces podríamos decir que está ordenada.

El ordenamiento de burbuja o bubble sort, es uno de los algoritmos de ejemplo, para la introducción a las ciencias computacionales.

Dejo esta url para los que no han entendido muy bien el tema de Big O Notation, viene muy bien explicado https://medium.com/@charlie_fuentes/notacion-big-0-para-principiantes-f9cbb4b6bec8

El ordenamiento de burbuja es un algoritmo de ordenamiento que nos permite colocar los elementos de una lista o vector en una secuencia dada, ya sea de mayor a menor, o de menor a mayor.

Este algoritmo 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.

Código ordenamiento burbuja. Incluyo contador de ejecuciones.

import random

def ordenamiento_burbuja(lista):
    contador=0
    n = len(lista)
    for i in range(0,n):
        for j in range(0,n-i-1):
            print(f'Ejecución para i: {i} y j: {j} Ejecución número: {contador}')
            contador+=1
            if lista[j]>lista[j+1]:
                lista[j],lista[j+1] = lista[j+1],lista[j]
                # Es lo mismo que hacer:
                # temporal=lista[j+1]
                # lista[j+1]=lista[j]
                # lista[j]=temporal
        
     return (lista,contador)

if __name__=='__main__':

    tamano_lista = int(input('Por favor ingrese el tamaño de la lista: '))
    lista = [random.randint(0,100) for i in range(0,tamano_lista)]
    print(lista)
    tupla_ordenada=ordenamiento_burbuja(lista)
    print(tupla_ordenada[0])
    print(f'La ejecución se realizó {tupla_ordenada[1]} veces')

Hermano, yo antes de ver el código del profe, me puse como ejercicio hacer el ordenamiento según cómo lo veía en la animación, y kchen:

PD: Me encantaría compartir el código, pero como que se pierde el formato en el preview

Agregue comentarios, me ayudaron a entender mejor este algoritmo 😃

import random

def ordenamiento_de_burbuja(lista):
    n = len(lista) # O(1)
    # lista = [1,2,3,4,5,6]

    for i in range (n): # O(n)
        # i1 = 0 # i2 = 1 ...
        for j in range(0, n - i - 1): # O(n - i - 1)
            # (0, 6 - 0 - 1) = (0, 5) # (0, 6 - 1 - 1) = (0, 4) ...
            # j1 = [0,1,2,3,4]        # j2 = [0,1,2,3] ...
            if lista[j] > lista [j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    # O(n) * O(n - i - 1) = O(n) * O(n) = O(n**2)

    return lista # O(1)

    # O(1) + O(n**2) + O(1) = O(n**2)

if __name__=='__main__':

    tamano_lista = int(input('De que tamano sera la lista? '))

    lista = [random.randint(0,100) for i in range(tamano_lista)]
    print(lista)

    lista_ordenada = ordenamiento_de_burbuja(lista)
    print(lista_ordenada)

Maravillosa clase aunque me quedó una duda ¿Se pueden imprimir todos los pasos que hace la burbuja para ordenar la lista?

Aquí pueden ver una entrada de un compañero del curso sobre Buble Sort

Ordenamiento de burbuja:
*El ordenamiento de burbuja es un algoritmo que recorre repetidamente una lista que necesita ordenarse. Compara elementos adyacentes y los intercambia si están en el orden incorrecto. Este procedimiento se repite hasta que no se requieren más intercambios, lo que indica que la lista se encuentra ordenada.

pregunta eso se apolica tambien a web scrapping??

import random

def ordenamiento_de_burbuja(lista):
    n = len(lista)

    for i in range(n): #n es la cantidad de caracteres de mi lista
        for j in range(0, n - i - 1):

            if lista[j] > lista[j+1]:
                lista[j], lista[j+1] = lista[j+1], lista[j] #Estamos intercambiando los valores
            
    return lista


if __name__ == "__main__":
    tamano_de_lista = int(input("¿Cuál es el tamaño de la lista?: "))

    lista = [random.randint(0,100) for i in range(tamano_de_lista)]
    print(lista)

    lista_ordenada = ordenamiento_de_burbuja(lista)
    print(lista_ordenada)

Muy buena clase soy muy nuevo en todo esto y lo entendí perfecto!

Me gustó mucho este algoritmo, gracias !

Sé que esto es trivial pero, ¿alguien sabe qué SO o dock utiliza David?
Me gusta mucho el diseño y no lo había visto antes.

con 10000 elementos tardó 12.016309976577759 y con 100000 tardó… NO LO SÉ!! ESPERÉ ALREDEDOR DE 15 MINUTOS Y NUNCA TERMINÓ

Ahora sí entiendo la complejidad, antes de este curso hubiese pensado que tardaría solo 10 veces más

Pensé que era una complejidad logarítmica

Me encanto el concepto de swapping, no había caído en cuenta

Si escribimos que no imprima ‘iteracion’ en cada iteracion de ‘i’ podemos ver como se ordena cada vez que se mueve entre la lista, y como cada vez es mas pequeño el recorrido

How long will the list be? 10
[10, 100, 79, 32, 87, 64, 52, 29, 50, 13]
iteracion
[10, 79, 100, 32, 87, 64, 52, 29, 50, 13]
[10, 79, 32, 100, 87, 64, 52, 29, 50, 13]
[10, 79, 32, 87, 100, 64, 52, 29, 50, 13]
[10, 79, 32, 87, 64, 100, 52, 29, 50, 13]
[10, 79, 32, 87, 64, 52, 100, 29, 50, 13]
[10, 79, 32, 87, 64, 52, 29, 100, 50, 13]
[10, 79, 32, 87, 64, 52, 29, 50, 100, 13]
[10, 79, 32, 87, 64, 52, 29, 50, 13, 100]
iteracion
[10, 32, 79, 87, 64, 52, 29, 50, 13, 100]
[10, 32, 79, 64, 87, 52, 29, 50, 13, 100]
[10, 32, 79, 64, 52, 87, 29, 50, 13, 100]
[10, 32, 79, 64, 52, 29, 87, 50, 13, 100]
[10, 32, 79, 64, 52, 29, 50, 87, 13, 100]
[10, 32, 79, 64, 52, 29, 50, 13, 87, 100]
iteracion
[10, 32, 64, 79, 52, 29, 50, 13, 87, 100]
[10, 32, 64, 52, 79, 29, 50, 13, 87, 100]
[10, 32, 64, 52, 29, 79, 50, 13, 87, 100]
[10, 32, 64, 52, 29, 50, 79, 13, 87, 100]
[10, 32, 64, 52, 29, 50, 13, 79, 87, 100]
iteracion
[10, 32, 52, 64, 29, 50, 13, 79, 87, 100]
[10, 32, 52, 29, 64, 50, 13, 79, 87, 100]
[10, 32, 52, 29, 50, 64, 13, 79, 87, 100]
[10, 32, 52, 29, 50, 13, 64, 79, 87, 100]
iteracion
[10, 32, 29, 52, 50, 13, 64, 79, 87, 100]
[10, 32, 29, 50, 52, 13, 64, 79, 87, 100]
[10, 32, 29, 50, 13, 52, 64, 79, 87, 100]
iteracion
[10, 29, 32, 50, 13, 52, 64, 79, 87, 100]
[10, 29, 32, 13, 50, 52, 64, 79, 87, 100]
iteracion
[10, 29, 13, 32, 50, 52, 64, 79, 87, 100]
iteracion
[10, 13, 29, 32, 50, 52, 64, 79, 87, 100]
iteracion
iteracion
[10, 13, 29, 32, 50, 52, 64, 79, 87, 100]```

Sobre la pregunta de la complejidad algoritmica del método burbuja, pienso que es n veces el número de elementos del arreglo multiplicado por (n-1)!, en otros terminos la CA= n(n-1)!, si no favor de corregirme en esto.

Este algorítmo se puede optimizar si se para cuando en el cilo for no hay ningún cambio de números. Les dejo más sobre este algorítmo:

https://www.geeksforgeeks.org/bubble-sort/

Hay varias cosas que me escaman, como no poder cambiar i o j como quiero, los if anidados para añadir varias conidiciones, pero bueno con esto he conseguido acortar el tiempo de ejecucion a la mitad

def bucles(lista):
    tamaño_lista = len(lista)
    global pasadas
    global operaciones
    max_number = 0
    min_number = 100
    position_min_number=0
    position_max_number=0

    j=0
    n=0

    for i in range(tamaño_lista//2):        
        
        while j < tamaño_lista - n:
            if lista[j] > max_number:
                max_number = lista[j]
                position_max_number = j
                #print(f'Mayor numero encontrado = {max_number}')

            if min_number > lista[j]:
                min_number = lista[j]
                position_min_number = j
                #print(f'Menor numero encontrado = {min_number}')
            j+=1
        n+=1
        j=i+1        

        if position_min_number != i :
            lista[position_min_number] = lista[i]            
            lista[i] = min_number                        
            #print(f'{lista} caso de minimo')

        if position_max_number != position_min_number:
            if position_max_number != i: 
                lista[position_max_number] = lista[tamano_de_lista - i -1]            
                lista[tamano_de_lista - i -1] = max_number
                #print(f'{lista} caso de maximo')                    

        if position_max_number == i:           
            lista[position_min_number] = lista[tamano_de_lista - i -1]            
            lista[tamano_de_lista - i -1] = max_number            
            #print(f'{lista} caso de maximo == i')
                 
        max_number = 0
        min_number = 101

    lista_ordenada = lista

    return lista_ordenada      

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.

Lo hice antes de ver la clase, y luego me di cuenta de que el mío tarda más debido a que recorre toda la lista en cada iteración.

def bubble_sort(ulist):
    sorted_pairs = None
    movements = 0
    while sorted_pairs != 0:
        sorted_pairs = 0
        for i in range(len(ulist)-1):
            if ulist[i+1] < ulist[i]:
                ulist.insert(i, ulist[i+1])
                del ulist[i+2]
                sorted_pairs += 1
        
        movements += sorted_pairs
    print(f'Movements = {movements}')```

Aun que la categoria del algoritmo entre de n^2 en realidad el numero de iteraciones es un poco mejor a lo mencionado ya que el algoritmo necesita
n^2/2 - ~0.6n
O al menos esa es la que obtiene el programa que yo hice

import os, random
pasos = 0
def burbuja(lista):
    global pasos
    # os.system('clear')
    # print(lista)
    # input('Presiones una tecla para continuar ...')
    for j in range(len(lista) - 2):
        for i in range(len(lista) - j - 1 ):
            if lista[i] > lista[i+1]:
                lista[i], lista[i+1] = lista[ i+1 ], lista[i]
            pasos += 1
            # os.system('clear')
            # print(lista)
            # input('Presione una tecla para continuar ...')
    return lista

if __name__ == '__main__':
    tamano_lista = int(input('Ingrese el tamaño de la lista:   '))
    lista = [random.randint(0, 100) for elemento in range(tamano_lista)]
    print(lista)
    print(burbuja(lista))
    print(f'La lista se ordeno en  {pasos} pasos')

import random
pasos = 0

def burbuja(lista):

    global pasos

    n = len(lista)

    for i in range(n):
        for j in range(n - i - 1):
            
            if lista[j] > lista[j+1]:
                lista[j], lista[j+1] = lista[j+1], lista[j]

            pasos += 1


    return lista 

if __name__ == "__main__":
    tamano_de_lista=int(input('Ingrese el tamano de la lista: '))
    lista = [random.randint(0, 100) for elemento in range(tamano_de_lista)]
    print(lista)
    print(burbuja(lista))
    print(f'Pasos para ordenar la lista: {pasos}')```

Si en cada iteración, la lista a recorrer se hace más pequeña, por qué no es O(n log n)?