Aún no tienes acceso a esta clase

Crea una cuenta y continúa viendo este curso

Ordenamiento de burbuja

17/25
Recursos

Aportes 163

Preguntas 19

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesión.

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. 😎

Página para visualizar algoritmos de ordenamiento dependiendo de como estén organizados los datos de entrada. Por ejemplo: si están casi ordenados, están colocados de manera aleatoria, etc.

Es útil para ver la velocidad y saber qué algoritmo utilizar dependiendo del caso.
 
➡️ https://www.toptal.com/developers/sorting-algorithms
 

https://github.com/karlbehrensg/poo-y-algoritmos-python

Ordenamiento de burbuja

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.

import random


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)

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.

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)

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 8
8/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)

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

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;
}

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.

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.

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)

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 😃

Complejidad Algoritmica Ordenamiento de burbuja

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))

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.

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)

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)

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

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.

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?

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!

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

## 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

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')
    

Clases para buenas.

  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.

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')

Que placer programar con Python!
Swapping en Python 🐍 :

Swapping en Java ☕️:

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)?

Sería más eficiente si tengo un diccionario, lista o tupla de numeros ?? por ejemplo, tener todos los numeros del 1 al 1.000.000.000 y que vaya colocando los numeros en orden según el diccionario, lista o tupla.

Es interesante ver como van evolucionando estos algoritmos.

import random

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]
                lista[j] =lista[j +1]
                lista[j+1]=lista[j]
 return lista

if __name__=='__main__':
    tamano_de_la_lista = int (input('De que tamano sera la lista?  '))

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

    lista_ordenada=ordenamiento_de_burbuja(lista)
    print(lista_ordenada)

que es la complejidad algorítmica ?

Este curso es la caña diria el juego de guitar hero :v xd

tengo una duda. al intercambiar el elemento lo que intercambia es el elemento con índice y valor o solo el valor es lo que se intercabia?

Se me acaba de ocurrie un sistema de ordenamiento binario, haces una sola pasada hasta encontar el mayor, divides en dos y agrupas en dos grupos y asi sucesivamente.

Les dejo mi código más ineficiente pero que igual funciona xd


def ord_burbuja(lista):
    for y in lista:
        for i in range(len(lista)): 
            if i == 0 :
                mayor_termino = lista[0]
                menor_termino = 0
            else: 
                if lista[i] < mayor_termino: 
                    menor_termino = lista[i]
                    lista[i] = mayor_termino
                    lista[i-1] = menor_termino
                elif lista[i] > mayor_termino:
                    mayor_termino = lista[i]
                    menor_termino = lista[i-1]
    return lista

no2 la complejidad

Les dejo el código de burbuja y burbuja mejorada(uso de flag para romper ciclo en caso de no cambios) que nos ahorra un par de ciclos

import random

def burbujaMejorada(lista):
    contador=0
    n=len(lista)
    flag=True
    for i in range(n):
        contador+=1
        flag=False
        for j in range(0, n-1-i):
            if lista[j]>lista[j+1]:
                flag=True
                lista[j],lista[j+1]=lista[j+1],lista[j]
        if flag!=True:
            break
    return contador

def burbuja(lista):
    contador=0
    n=len(lista)
    for i in range(n):
        contador+=1
        for j in range(0, n-1-i):
            if lista[j]>lista[j+1]:
                lista[j],lista[j+1]=lista[j+1],lista[j]
    return contador

if __name__ == "__main__":
    tamano_de_lista= int(input('De que tamano sera la lista? \n'))
    lista=[random.randint(0,100) for i in range(tamano_de_lista)]
    print(lista)
    iteraciones=burbujaMejorada(lista)
    print(f'Luego de burbuja mejorada con un total de {iteraciones} interaciones')
    print(lista)
    iteraciones=burbuja(lista)
    print(f'Luego de burbuja con un total de {iteraciones} interaciones')
    print(lista)

MAXIMO TERMINO DE UNA LISTA

Para obtener el mayor elemento de una lista, tenemos 2 formas:
-max(lista)
-ordenamiento de burbuja

Cual es la diferencia?
Que max() lo podemos utilizar cuando nuestra unica tarea sera obtener el mayor elemento, ya que no es recomendable utilizar el ordenamiento de burbuja solo para saber el mayor elemento y ya.

Es recomendable utilizar el ordenamiento de burbuja para obtener el mayor elemento solo cuando se vaya a utilizar para mas tareas

¿Por que en el primer ciclo for del script el rango es n y no n - 1?

Ordenamiento de burbuja, ineficiente pero muy intuitivo

Comprendido!!!

# Quadratic or О(n**2)
def sort_list(list):
    """Given a list of unsorted numbers this function sort the list with the Bubble sort algorithm https://en.wikipedia.org/wiki/Bubble_sort
    Parameters:
        list (list<int>): unsorted list of numbers
    Returns:
        list: with sorted elements"""
    list_size = len(list)

    while list_size >= 1:
        last_list_element = 0

        for i in range(1,list_size):

            if list[i - 1] > list[i]:
                list[i - 1], list[i] = list[i], list[i - 1]
                last_list_element = i
                
        list_size = last_list_element

    return list

mi algoritmo reduce la redundancia aun asi sigue siendo nxn

<    def orden_burbuja(lista):#,ascendente=True
        
        tamaño = len(lista)
        for j in range(tamaño):
            for i in range(tamaño-1):
                if lista[i]>lista[i+1]: # esta en desorden ?
                    aux=lista[i+1] # guardar en auxiliar
                    lista[i+1]=lista[i] # depositamos 2 en 1
                    lista[i]=aux # depositamos aux en 1
            tamaño-=1 # disminuimos las iteraciones en -1
        return lista>

Ordenamiento Burbuja: Es un algoritmo de ordenación, lo que hace es recorrer la lista y va comparando elementos contiguos, y si están en una posición errada los intercambia, hace este recorrido tantas veces como errores encuentre.

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 tamaño 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)```
import random

def bubble_sort(lista):
    n_list = len(lista)
    for i in range(n_list):
        for j in range(0, n_list-1):
            if lista[j] > lista[j+1]:
                lista[j], lista[j+1] = lista[j+1], lista[j]

    return lista


if __name__ == '__main__':
    lenght = int(input('Captura la longitud de la lista:'))
    lista = [random.randint(0,100) for i in range (lenght)]
    print('La lista desordenada es: {}'.format(lista))

    resultado = bubble_sort(lista)
    print('La lista ordenada es: {}'.format(resultado))

Muy interesante como poder ordenar las listas, seguramente el ordenamiento por inserción será más eficiente!!