Ordenamiento por Mezcla: Algoritmo y Conceptos Básicos
Contenido del curso
Michelle Osorio
Johan Mora
Iván Godoy
Joel Eduardo Gaspar
Iván Godoy
Cesar Hernández Ramírez
Johan Labrada
Reinaldo Orozco
Gonzalo Ferrando
Jorge Rafael Sarabia
Francisco Javier Mendoza Flores
Marcelo Sánchez
Jose Colmenares
Juan Diego Ramirez
Maria Aurora Molina Vilchis
Usuario anónimo
User
Daniel Montes
Maria Guadalupe Diaz Escobar
Guillermo Garcia Beverido
Guillermo Garcia Beverido
Karl Behrens Gil
Nicolás Peralta Páez
Lorenzo Enrique Piñango Cerezo
Iván Ricardo Bohórquez Basto
Miguel Andres Rendon Reyes
Santiago Caldevila
Omar Garrido García
Gabriel Delgadillo Romero
Juan Diego Bohorquez Quiroga
Gerardo Ruben Marin Riveroll
Sergio Andrés Pachón Dotor
Lorenzo Enrique Piñango Cerezo
Angel Armando Martínez Blanco
Mateo Echavarria
Juan Fernando Moyano Ramírez
Oscar Hernan Pomi Piazza
Manuel Alejandro Hermoso
Jose Carlos Borrayo
Gustavo Esquivel Sosa
Jose Diego Alvarez Paredes
Vicente Fernandez
Andres Gonzalez
Beder Danilo Casa Condori
Diego Andres Martelo Hernandez
Beder Danilo Casa Condori
Maicol Steven Argumedo Martinez
Paola Duran
Marlon Ramirez
Cecilio Cauich
Edgar Eusebio Marin Parra
Josué Esteban Cordero Ruvalcaba
Hector Saldaña Espinoza
Alexis Toro Navarro
CRISTIAN BARBERO PÉREZ
Alejandro Aguilar
Saber programar es facil, saber pensar es lo difícil.
Comparto su pensamiento caballero
Tienes la razón, aquí está el valor agregado.
Aumento su ki de golpe! jajaja esto se puso más serio
Jajaja, si. Hasta ahora todo iba bien.
Asi es jajaj :(
hice un gráfico de cómo funciona la recursividad en este algoritmo, con una lista pequeña (5,4,8,2), a mí me ayudó a entenderlo más fácil, tal vez a alguien le sirva xd
Me fue de gran ayuda tu aporte muchas gracias.
Excelente compañero!
Tal vez este comentario le sirva a alguien... Yo había olvidado que las listas en Python se pasan por referencia. Lo cual quiere decir, que si modificamos la lista dentro de la función, también lo hacemos en la lista original...
¡Gracias!
Para que eso no te suceda te recomiendo que utilices el comando
.copy()
Voy por las 20 veces viéndolo, espero no tener que llegar a las 100 para entenderlo.
Revisa que tengas claro el concepto de recursividad. Yo volví a ver la clase de recursividad, volvi a ver esta construyendo el codigo paso a paso, y todo fue mucho mas claro
a mi me pasó con el anterior, lo leí como 7 veces, ya estaba desanimándome
Para los que loquieran ver de una manera mas grafica: https://visualgo.net/en/sorting
Gracias!
Gracias
Heme aqui, casi a las 2AM leyendo y releyendo mi codigo el cual ya entendi como funciona, lo redacte y copie igual a como muchos lo tienen aqui...y mi cerebro esta colapsano un poco que nomas no lo organiza, y ahora cada que lo imprimo literal me modifica los valores. Aplicare la vieja y confiable, me voy a dormir un rato y regreso a darle otra checada, ya que este fresque como lechuge.
y efectivamente, ya me salio bien haha
https://github.com/karlbehrensg/poo-y-algoritmos-python
Ordenamiento por mezcla
El ordenamiento por mezcla creado por John von Neumann el cual aplica el concepto de "divide y conquista". Primero divide una lista en partes iguales hasta que quedan sublistas de 1 o 0 elementos. Luego las recombina en forma ordenada.
import random def ordenamiento_por_mezcla(lista): if len(lista) > 1: medio = len(lista) // 2 izquierda = lista[:medio] derecha = lista[medio:] print(izquierda, '*' * 5, derecha) # llamada recursiva en cada mitad ordenamiento_por_mezcla(izquierda) ordenamiento_por_mezcla(derecha) # Iteradores para recorrer las dos sublistas i = 0 j = 0 # Iterador para la lista principal k = 0 while i < len(izquierda) and j < len(derecha): if izquierda[i] < derecha[j]: lista[k] = izquierda[i] i += 1 else: lista[k] = derecha[j] j += 1 k += 1 while i < len(izquierda): lista[k] = izquierda[i] i += 1 k +=1 while j < len(derecha): lista[k] = derecha[j] j += 1 k += 1 print(f'izquierda {izquierda}, derecha {derecha}') print(lista) print('-' * 50) 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) print('-' * 20) lista_ordenada = ordenamiento_por_mezcla(lista) print(lista_ordenada)
Excelente aporte. Siempre por aquí buscando tus apuntes, jeje
Excelente aporte :)
Asumí que el código haría simultáneamente el ordenamiento, tanto de la lista izquierda como el de la derecha, así como cuando al inicio de esta clase se muestra el ejemplo.
Al ver por print statements como se ejecuta el paso a paso, me quedó mucho más claro. Ahora, la idea es leer este código y comprenderlo mejor.
Dijo Freddy Vega que la mayor parte del tiempo un programador la pasa leyendo código de otros. Así que eso haré.
A
i
CHICOS Si tienen problemas para entender el algoritmo les dejo este vídeo muy bueno que te explica paso a paso para que le entiendan, el código es muy parecido al de la clase
Me sirvio un monton este video, tiene un codigo mas claro y me ayudo a verlo de manera mas simple. Gracias por compartirlo
Excelente video, dejo el código del vídeo para que lo puedan analizar, realmente es mucho mas cómodo de leer que el estudiado en la clase.
import random def ordenamiento_por_mezcla(lista): mid = len(lista)//2 if len(lista) > 1: L = lista[mid:] R = lista[:mid] lista.clear() ordenamiento_por_mezcla(L) ordenamiento_por_mezcla(R) while len(L) > 0 and len(R) > 0: if L[0] < R[0]: lista.append(L.pop(0)) else: lista.append(R.pop(0)) while len(L) > 0: lista.append(L.pop(0)) while len(R) > 0: lista.append(R.pop(0)) 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) print('-' * 20) lista_ordenada = ordenamiento_por_mezcla(lista) print(lista_ordenada)
Hola! Este código no es mio, pero pensé en compartirlo porque se trata de un algoritmo muy similar pero implementado de una forma muy elegante, se está haciendo básicamente lo mismo, pero con menos líneas de código:
def quicksort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quicksort(left) + middle + quicksort(right) print (quicksort([35,8,58,68,65,42,93,86,2,1,90])) # Prints "[1, 2, 8, 35, 42, 58, 65, 68, 86, 90, 93]"
PD Lo modifiqué un poco para que fuera compatible con Python 3.
https://github.com/tuanavu/Stanford-CS231/blob/master/notes/0-preparation/python-numpy-tutorial.md
Excelente aporte, el nivel de abstracción y uso de python en este caso es increíble!!!
Muy buen aporte
El código me confunde un poco en la parte de las funciones de recursión. Verán, en general, la función ordenamiento_por_lista() tiene un return. Cuando se está ejecutando y se llaman a las funciones no hay variable alguna a la cual se vaya a guardar el resultado final.
return lista
Para mi mejor entendimiento (sé que algunos le entendieron a la primera, pero en mi caso esto me ayuda) reescribí el código de la siguiente manera:
def ord_por_mezcla(lista): #caso base if len(lista) > 1: medio = len(lista) // 2 izquierda = lista[:medio] derecha = lista[medio:] print(izquierda, '*' * 5, derecha) #llamada recursiva izquierda = ord_por_mezcla(izquierda) derecha = ord_por_mezcla(derecha) #iteradores para recorrer las dos sublistas i = 0 j = 0 #Iterador para la lista principal k = 0 while i< len(izquierda) and j < len(derecha): #mientras podamos seguir comparando if izquierda[i] < derecha[j]: lista[k] = izquierda[i] i += 1 else: lista[k] = derecha[j] j += 1 k+= 1 #copiar los pedazos de las listas que quedaron while i < len(izquierda): lista[k] = izquierda[i] i+=1 k += 1 while j < len(derecha): lista[k] = derecha[j] j += 1 k += 1 print(f'izquierda {izquierda}. derecha {derecha}') print(lista) print('--' * 30) return lista
Exacto el primer while solo se ejecuta si existe un mayor y un menor con quien comparar sino se agrega automáticamente como el mayor de la lista
Hola, tu codigo me ha ayudado mucho a entender mejor el funcionamiento del algoritmo, Gracias
minuto 09:17 -> indica que para que el while no se valla al infinito manda un k +=1 cosa que no es cierto, por que el while nunca se va a ir a infinito por que depende de i y j y en cualquier caso siempre aumentan pero no mas que la longitud finita de izq o der. en cualquier caso hay que poner el k +=1 para seguir moviendose en la lista no guardar todo en la mismo lugar de lista [k=0]
buena aclaración, correcto el k += 1 es solo para guardar los valores en la posición correcta de la lista.
¡Gracias! Estuve un buen rato pensando en por qué el k limitaría la lista. Buen aporte.
Les dejo una imagen que me ayudo a entender un poco mejor el codigo.
Y bueno, la primer imagen que aparece si buscas merge sort, pero igual me ayudo. xd
Este aporte es genial!
No lo entendí y le dedique bastante tiempo. La verdad pienso que esta muy mal explicado.
la verdad el profesor como que no explica lo suficiente en sus cursos
al inicio es dificil entenderlo, pero ayudate con otros videos
Les dejo este pequeño diagrama con un ejemplo de como funcional el algoritmo, le faltan por especificar varios detalles pero pensé que a alguno le podría servir para entender.
mmmm
Diego me ayudó muchisimo tu diagrama, sobre todo el tema de los aumentos de las i; j ; k y como luego de tener dos sub listas en el paso 8, se iban comparando. Saludos y gracias!
Hola, aquí dejo un enlace con la visualización de distintos algoritmos de ordenamiento, que les puede ser muy útil para entenderlos. Puede ayudar a entender la pila de recursividad del merge sort. https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/visualize/
Muchas gracias, excelente herramienta
Gracias me fue de mucha ayuda!
este es el tema mas complejo que he visto hasta ahora. solo me da animo escuchar lo que el profe dice, que no importa si lo tengo que leer hasta 10.000 veces con tal que lo entienda
El big O de los diferentes algoritmos de ordenamiento tanto en tiempo como en memoria
Excelente aporte!
donde se guarda lo que retorna la recursividad ? en la misma lista?
Sí, más o menos, cada lista se devuelve ordenada a la lista de la que salió.
Con la recursividad vas bajando en el siguiente árbol, una vez que llegas abajo del todo se produce el ordenamiento y se recorre el árbol hacia arriba.
Por ejemplo, el 3 y el 9 se cambiarían de sitio abajo del todo y eso se guardaría en el array [9, 3] que pasaría a ser [3, 9]
Esto pasa porque recuerda que la lista es un objeto mutable por lo tanto cuando tu envías a la función interna la lista, realmente lo que pasa adentro es que trabaja DIRECTAMENTE con la lista que está en memoría, recomiendo que hagas este ejercicio para que te quede mas claro:
print(id(lista)) # 1904915618944 lista_ordenada = ordenamiento_por_mezcla(lista) print(id(lista_ordenada)) # 1904915618944 print(lista_ordenada)
Nota que a pesar de que son 2 variables distintas, ambas listas tienen el mismo identificador, esto significa que internamente (dentro de memoria) son lo mismo (sólo que con otro nombre)
ordenamiento_por_mezcla(izquierda)
Puedes estar seguro que la lista "izquierda" al ser un elemento mutable, va a usar el mismo espacio en memoría y haría exactamente lo mismo a que si hicieras:
izquierda = ordenamiento_por_mezcla(izquierda)
def ordenamiento_por_mezcla(lista): print(id(lista)) # 1904915618944
Todo esto porque es un objeto mutable, espero que te sirva tanto para ti, como para mi recordar como funcionan los objetos mutables, la verdad en un inicio yo también tuve la misma duda :D
