Clase 8 de 16 • Curso de Complejidad Algorítmica con Python
Contenido del curso
Ivan Santiago
Manuel Alejandro Hermoso
Luis Ruiz Ramos
Francisco Leví Méndez Delgado
David fernando Pinzon suarez
freddy molleda
Jose Flores
Alvaro Torres Sánchez
Mauricio Gonzalez Falcon
Antonio Demarco Bonino
Oscar Stanley Sandoval Rivera
JHØN AVALØZ
Alberto Sánchez
Cesar Hernández Ramírez
Mauricio Gonzalez Falcon
Mauricio Obe
Ignacio Consuegra
Luis Gerardo Cámara Salinas
Gonzalo Muñoz
ANDRES CONTRERAS MANCIPE
Gonzalo Brolyn Flores Bermejo
ANDRES CONTRERAS MANCIPE
Sebastian Calderón Araque
Mario Cabrera Vicencio
Fataë 🏴
Mario Cabrera Vicencio
Andres Felipe Zabala velez
Martín David Llauce Santos
Emilio Sala
Josue Granados
Gabriel Salvador
Gerardo Ruben Marin Riveroll
Gabriel Salvador
Fabricio Xavier Galárraga Pérez
Luis Fernando Pedroza Taborda
Michelle Verano
Alvaro Daniel Vidal Velasque
López Ary Dani
Gabriel Missael Barco
Walter Correa
Ronaldinhoo Farfan
Camilo Jaramillo
Juan Esteban Sierra Aguilar
Juan Esteban Sierra Aguilar
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. 😎
Gracias por el aporte! esta interesante el generador de gráficos de la pagina
Genial
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.
Se pone el return por legibilidad del código
es verdad!
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)
Buena observación, pero hay un pequeño error en tu análisis. No todos los triángulos cumplen que su base sea igual que su altura, además, como le vamos restando 1, se tendría: Con una lista de 7 elementos (7x6)/2 = 21 con una de 8 se tendría (8x7)/2 = 28 con una de 9 se tendría (9x8)/2 = 36 Aún así no me queda claro porque dices que esa área se relaciona con la complejidad algorítmica.
Gracias por el aporte. Aunque concuerdo con la observación de Alvaro.
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)
Muchas gracias, me sirvio de mucho!
Gracias, con este aporte queda visualmente mas entendible el proceso que realiza el código.
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
Disculpa, a que te refieres con buble y buble_propio
Jamás sabremos que es Bubble 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.
Si a un profesor de matemáticas le cuesta, ahora el resto de los mortales.
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 :)
Hola. Alguno me pordria explicar que sucede en la linea 8 de codigo del curso. for j in range(0, n - i - 1) Entiendo que 0 es el comienzo pero no entiendo por que n - i -1 es el final de la siguiente iterasion.
# Ejemplo: lista = [39, 19, 16, 23, 97] def ordenamiento_burbuja(lista): n = len(lista) # n = 5 # Primera iteracion para i for i in range(n): # i = 0, range = (0, 1, 2, 3, 4) donde n = 5 # Primera iteracion para j for j in range(0, n-i-1): # j=0, range=(0, 1, 2, 3) donde n=5, i=0, n-i-1 = 4 # El range es de 0 a 3, porque en el condicional if siguiente # j comparara cada 2 elementos adyacentes hasta el final # si no le quitamos una posicion # lista[j+1] sera lista[5] y ese valor no existe if lista[j] > lista[j+1]: # j=0, j+1=1, comparamos los 2 primeros elementos #lista[0] = 39, lista[1] = 19, 39 es mayor q 19, cambiamos su orden lista[j], lista[j+1] = lista[j+1], lista[j] # lista[0] = 19, lista[1] = 39 # Segunda iteracion para j for j in range(0, n-i-1): # j=1, range=(0, 1, 2, 3) donde n=5, i=0, n-i-1 = 4 if lista[j] > lista[j+1]: # j=1, j+1=2 #lista[1] = 39, lista[2] = 16, 39 es mayor q 16, cambiamos su orden lista[j], lista[j+1] = lista[j+1], lista[j] # lista[1] = 16, lista[2] = 39 # Tercera iteracion para j for j in range(0, n-i-1): # j=2, range=(0, 1, 2, 3) donde n=5, i=0, n-i-1 = 4 if lista[j] > lista[j+1]: # j=2, j+1=3 # lista[2] = 39, lista[3] = 23, 39 es mayor q 23, cambiamos su orden lista[j], lista[j+1] = lista[j+1], lista[j] # lista[2] = 23, lista[3] = 39 # Cuarta iteracion para j for j in range(0, n-i-1): # j=3, range=(0, 1, 2, 3) donde n=5, i=0, n-i-1 = 4 if lista[j] > lista[j+1]: # j=3, j+1=4, lista[4] es el ultimo elemento # de esa manera tenemos control del recorrido de la lista # lista[3] = 39, lista[4] = 97, 39 es menor q 97, NO cambiamos su orden # resultado actual iteracion lista = [19, 16, 23, 39, 97] # Segunda iteracion para i for i in range(n): # i = 1, range = (0, 1, 2, 3, 4) donde n = 5 # Primera iteracion para j for j in range(0, n-i-1): # j=0, range=(0, 1, 2) donde n=5, i=1, n-i-1 = 3 # El range es de 0 a 2, porque este ordenamiento garantiza que en cada iteracion # de i el ultimo elemento es el mayor de todos los elementos recorridos if lista[j] > lista[j+1]: # j=0, j+1=1, comparamos los 2 primeros elementos #lista[0] = 19, lista[1] = 16, 19 es mayor q 16, cambiamos su orden lista[j], lista[j+1] = lista[j+1], lista[j] # lista[0] = 16, lista[1] = 19
gracias me ayudo un monton muy claro!
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.
¿Por que son necesarios los algoritmos de ordenamiento, cuando podemos usar la función sort?
Son importantes cuando estás desarrollando programas muy complejos. Al final programar es hablar con la computadora y las computadoras pasan más del 50% del tiempo "ordenando" (por eso los españoles les llaman ordenadores 😂) entonces es importante conocer cuáles son los algoritmos que se usan para ordenar.
Y es muy importante en la estructura de datos, para manejar grandes cantidades de información es imprescindible estudiar la eficiencia de los algoritmos de ordenamiento, el tiempo que toman en ejecutarse, el costo en recurso computacional y sí te quieres dedicar a la programación de manera profesional, las empresas grandes te piden como requisito saber de algoritmos.
@Fatae Muchas gracias por tu respuesta, entonces a estudiarlo más a fondo.
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.
Hola Andres. El docente al comentar en la primera ronda hace referencia a la primera iteración, por lo tanto tu print deberías estar fuera del segudo loop. Te dejo el codigo. Espero te ayude.
import random def ordenamiento_burbuja(lista: list): """Complejidad: O(n**2) """ iteraciones = 0 len_lista = len(lista) for index in range(len_lista): for key in range(len_lista - index - 1): value = lista[key] value_comparate = lista[key + 1] if value > value_comparate: lista[key + 1], lista[key] = value, value_comparate iteraciones += 1 print(lista) return lista, iteraciones if __name__ == '__main__': tamano_lista = int(input('Ingrese el tamaño de la lista: ')) lista = [random.randint(0, 100) for _ in range(tamano_lista)] print(lista) list_ordenada, iteraciones = ordenamiento_burbuja(lista) print(f'Lista ordenada: {list_ordenada} - iteraciones: {iteraciones}')
lo que si he visto en varios profesores es la explicacion de por qué ponemos "-1" en el segundo bucle. es para no salirnos de la lista porque hacemos un "j+1" y no porque estamos usando indices que inician de cero ya que range(n) no es n inclusivo. por eso en el primer bucle no es necesario poner -1
Que placer programar con Python! Swapping en Python 🐍 :
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)
Hola! Realmente estoy viendo un comportamiento
de tu código y de hecho del de la clase noté muy particular con el que me he topado por las malas y que también se trata en el curso previo a este. Te invito a que lo compruebes pero es lo siguiente, en la parte que asignas:
lista_1=lista
lista_2=lista
Lo que realmente acabas de hacer es asignar lista, lista_1 y lista_2 a apuntar al mismo lugar en memoria en lugar de copiar las listas en distintos, lugares. ¿Esto qué significa? Los cambios que le hagas a una les pasa a todas porque todas lo están buscando en el mismo lugar. Entonces cuando pasas la lista_2 al ordenamiento de la clase, la lista ya está ordenada!! Por eso seguramente es mucho más rápido el de la clase que el que hiciste, pero sólo por eso.
Cierto, no habia visto ese error
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
Fabricio apoyo su idea, en python si fue bastante sencillo hacerlo y entenderlo.
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.
.
Excelente aporte, no había pensado a profundadas todo aquellos conceptos planteados por usted compañero, me has resuelto un problema que todavía no habia solucionado. Saludos 😄
Ordenamiento de burbuja.
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
hola como hacer para verlo en forma grafica
Hola en mi caso aplicando todos los conocimientos de la clase, el ejercicio me está organizando casi todos los valores pero deja por fuera alguno.
Mi código es:
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 será 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)
y el print es:
Ej 1:
De que tamaño será la lista? 5 [84, 9, 99, 40, 82] [9, 84, 40, 82, 99]
Ej 2: De que tamaño será la lista? 10 [24, 28, 48, 34, 93, 88, 10, 65, 99, 31] [24, 28, 34, 48, 88, 10, 65, 93, 31, 99]
Saludos.
Por alguna razón tienes un problema con el espaciado/tabulado entre los ciclos for, ambos ciclo se están ejecutando una sola vez, es decir no están quedando anidados.
Ampliando la discusión, copié tu códgo y le agrregue un print para ver como estaban trabajando los ciclos.
!Imgur
