A煤n no tienes acceso a esta clase

Crea una cuenta y contin煤a viendo este curso

Ordenamiento por mezcla

19/25
Recursos

Aportes 252

Preguntas 62

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesi贸n.

Saber programar es facil, saber pensar es lo dif铆cil.

Aumento su ki de golpe! jajaja esto se puso m谩s serio

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

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鈥

Recomiendo este video, en mi opini贸n explica muy bien este algoritmo. https://www.youtube.com/watch?v=XaqR3G_NVoo

Voy por las 20 veces vi茅ndolo, espero no tener que llegar a las 100 para entenderlo.

Para los que loquieran ver de una manera mas grafica: https://visualgo.net/en/sorting

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

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 鈥渄ivide 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)

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

https://www.youtube.com/watch?v=FjOwTbOy18M

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

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鈥 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.

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

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.

No lo entend铆 y le dedique bastante tiempo. La verdad pienso que esta muy mal explicado.

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

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/

Es normal que esta clase se haga un poco dif铆cil, a mi me ayudo mucho volver a ver la clase de recursividad del curso pasado
https://platzi.com/clases/1764-python-cs/25243-recursividad/

La verdad es que estuve literalmente una hora viendo el codigo para entenderlo al 100%, me habia olvidado de como funcionaba el almacenamiento de listas, pero al final pude agarrarle la mano jajaja todo es cuestion de paciencia

Para mi el c贸digo se divide en estas secciones:

1.- Divide las listas hasta el minimo
2.- Compara los elementos y ordena
3.- (La seccion de los 2 while) Pone el ultimo elemento ya sea de izquierda o derecha

Creo que como todos la manera de entender es que pensabamos que el computador iba a hacer todo como nosotros lo hacemos en la cabeza y era que lo iba a hacer simultaneamente derecha e izquierda, pero viendo como funciona es lo maximo. Es una explosion mental

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

Chicos, por fa me pueden ayudar con una inquietud.

Cuando hace las llamadas de recursividad, esta ordenando las listas izquierda y derecha 驴verdad?

Por lo tanto me surge una pregunta. 驴Por qu茅 NO se escribe el codigo de recursividad de la siguiente manera?:

izquierda = ordenamiento_por_mezcla(izquierda)
derecha = ordenamiento_por_mezcla(derecha)

Acaso 驴esto sucede porque la lista (izquierda o derecha) utiliza el mismo espacio en memoria? o 驴por que?

El big O de los diferentes algoritmos de ordenamiento tanto en tiempo como en memoria

hice mi version de lo que entendi y queria saber si el pop hace que gaste mas recursos

from random import randint 

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

    if n <=1:
        return lista
    else:
        medio = n //2
        l1 = por_mescla(lista[:medio])
        l2 = por_mescla(lista[medio:])

        lista_final = []
        print(f'llega {lista}')
        print(f'{lista[:medio]} se convierte en {l1}')
        print(f'{lista[medio:]} se convierte en {l2}')
        print(n)

        for i in range(n):
            if len(l1) == 0:
                lista_final += l2
                break

            elif len(l2) == 0:
                lista_final += l1
                break

            elif l1[0] <= l2[0]:
                lista_final.append(l1[0])
                l1.pop(0)

            elif l1[0] > l2[0]:
                lista_final.append(l2[0])
                l2.pop(0)

        print(f'final{lista_final}')
        print('-'*50)
        return lista_final

aqui veran como funciona este algoritmo con un poco de baile

Esta muy bueno este c贸digo es 鈥渉ermoso鈥.

Al comparar los tres algoritmos de ordenamiento que vimos en el curso, si es concluyente que el de mezcla es mas r谩pido.
Dejo el link de el c贸digo que utilic茅 GitHub

PDTA: Si est谩 bien complicado el de mezcla haha vi el video varias veces !

Entiendo la recursividad pero lo que me falta por comprender son las variables i,j,k hahaha xd, a leer el codigo mil veces voy馃槄

entiendo el concepto pero no el codigo

Est谩bamos programando tranquilos y de repente me sueltan esto. No me haga esto oiga麓.

No tienen un curso de c贸mo desbloquear tu cerebro despu茅s de estas clases?

Me resulto dif铆cil entender el c贸digo y principalmente fue por la recursividad. Para entenderlo, tuve que recurrir a realizar un esquema del funcionamiento del c贸digo. A continuaci贸n lo publico, es probable que otra persona le suceda lo mismo.

He notado que somos unos cuantos a los que nos ocurre que comprendemos la l贸gica detr谩s de los algoritmos, pero su implementaci贸n a c贸digo usando los ejemplos del profesor nos cuesta trabajo.
Una recomendaci贸n personal que puedo hacer a cualquiera que este siguiendo el curso y le cueste, como a m铆, entender los c贸digos. Es quedarse con la explicaci贸n conceptual del profesor, interiorizarla y despu茅s complementar con tutoriales en internet de la implementaci贸n del c贸digo.
B谩sicamente por que el fuerte del profesor David, es transmitir el razonamiento detr谩s de los algoritmos, pero decae un poquito en cuanto a que tan legible es el c贸digo para gente que reci茅n comienza en la programaci贸n.
Y en la gran mayor铆a de los tutoriales de internet, los c贸digos son mucho m谩s expl铆citos, y amigables para su lectura e interpretaci贸n, pero casi nunca profundizan en la parte l贸gica tras los algoritmos.
Personalmente me esta ayudando mucho a no atascarme.
Aqu铆 un ejemplo del video que utilic茅 para entender el c贸digo de merge_sort.
https://www.youtube.com/watch?v=Lk5Ql4_VeUs

soy el unico que entiende el algortimo, pero no entiende por que el codigo mostrado funciona?

En este momento, me pareci贸 bien un repaso por el c贸digo de Recursividad b谩sico (con factorial) #volver a las bases.
Capaz a alguien le sirva:

# definici贸n de factorial expresado de tres maneras (pseudoc贸digo) para tener a  mano antes de empezar el c贸digo

factorial =  n * factorial de n-1 
factorial = n * (n-1)! 
factorial =  n * factorial(n-1)


#comienza el c贸digo:

def factorial(n):

    print("Entra a la funci贸n factorial, n vale: ", n)

    if (n > 1):
    
        #Si n es mayor a 1, entonces se vuelve a llamar la funci贸n que multiplica a n * (n -1)

        print("Como es mayor a 1, la funci贸n se llamara a si misma otra vez.\n")

        return n * factorial(n-1) # aqu铆 se est谩 llamando a s铆 misma
    
    else:
    
        #Si n es igual 1, ya no se llama la funci贸 a s铆 misma y terminar谩 la recursividad.

        print("n es igual a 1, termina la recursividad.\n")
        return 1
    


if __name__ == '__main__':

    print("\nRecursividad - Factorial\n\n")

    res = factorial(5)
    print("\nEl resultado es:  \n\n", res)

    



Hice una comparaci贸n de todos los algoritmos que vimos seg煤n la cantidad de elementos del arreglo y el tiempo (en segundos) que tardan. Esto usando el m茅todo de tomar el tiempo ante y despu茅s de aplicar el algoritmo y despu茅s sacar la diferencia.
(Los que est谩n con signos de pregunta tardaban demasiado tiempo o se me trabo la computadora en medio de la espera)

  • B煤squeda Lineal: T(n) = O(n)
    Elementos Tiempo
    1.000 -> 0,0
    10.000 -> 0,001
    100.000 -> 0,005
    1.000.000 -> 0,032
    10.000.000 -> 0,306
    100.000.000 -> 3,894
    1.000.000.000 -> ???

  • Busqueda Binaria: T(n) = o(log n)
    Elementos Tiempo
    1.000 -> 0,0
    10.000 -> 0,0009
    100.000 -> 0,003
    1.000.000 -> 0,032
    10.000.000 -> 0,317
    100.000.000 -> 3,249
    1.000.000.000 -> ???

  • Bubble Sort: T(n) = O(n^2)
    Elementos Tiempo
    100 -> 0.002
    1.000 -> 0,093
    10.000 -> 10,65
    100.000 -> 1031.36
    1.000.000 -> ???

  • Insert Sort: T(n) = O(n^2)
    Elementos Tiempo
    100 -> 0.0
    1.000 -> 0,055
    10.000 -> 5,53
    100.000 -> 586.36
    1.000.000 -> ???

  • Merge Sort: T(n) = O(n log n)
    Elementos Tiempo
    100 -> 0.0
    1.000 -> 0,003
    10.000 -> 0,058
    100.000 -> 0,663
    1.000.000 -> 7,809
    10.000.000 -> 91,093
    100.000.000 -> ???

a mi se me hace mas intuitivo asi:

def merge_sort(lista):
    
    if len(lista) <= 1:
        return lista

    middle = len(lista) // 2

    left = merge_sort(lista[:middle])
    right = merge_sort(lista[middle:])

    temp_list = []

    while len(left) > 0 and len(right) > 0:

        if right[0] < left[0]:
            temp_list.append(right[0])
            del right[0]
        else:
            temp_list.append(left[0])
            del left[0]
    
    temp_list.extend(left)
    temp_list.extend(right)

    return temp_list

Quiero hacer un aporte ya sea que creo que es un poco b谩sico, pero ah铆 les va para alguien que tenga la misma duda que yo:
Yo llegaba a entenderlo conceptualmente pero ten铆a una duda en el c贸digo especificamente en esta parte cuando se llamaba recursivamente:

ordenamiento_por_mezcla(izquierda)
ordenamiento_por_mezcla(derecha)

como solo se llamaba y no almacenaba en ninguna variable para no perder los datos como era mi l贸gica, ejemplo:

# Observaci贸n: asi tambien funciona :)
izquierda = ordenamiento_por_mezcla(izquierda)
derecha = ordenamiento_por_mezcla(derecha)

yo cre铆a que los valores se perdian al no ser guardados y supuestamente no tendr铆a que ordenarse, pero luego record茅 la clase de scope(alcance de variables) me di cuenta que lo que se modificaba en cada llamada correspondia a cada variable sin necesidad de explicitamente asignarla. En esta parte todo lo que se modifique dentro de la funci贸n afectar谩 a cada variable ya que tienen el mismo id, puedes corroborarlo a trav茅s de los print statement :

# As铆 es como me di cuenta :)
print(id(merge_sort(left)), id(left), id(right))
print(id(merge_sort(right)), id(left), id(right))

con esto logr茅 resolver la duda que ten铆a, espero les sirva de ayuda y si me equivoque en algo por favor que lo explique en los comentarios para que todos podamos entender.

Creo que me complique un poco 鈥 馃憖

def merge_sort(lista):
    if len(lista) > 1:
        mitad = len(lista)//2
        aux_list=[]
        listas = [merge_sort(lista[:mitad]),merge_sort(lista[mitad:])]
        size_lists= [len(listas[0]),len(listas[1])] 
        flag = 0 if size_lists[0] > size_lists[1] else 1
        max_list = listas[flag]
        min_list = listas[abs(flag-1)]
        count_maxlist, count_minlist = 0, 0
        for i in range(len(max_list)):
            if count_minlist <= len(min_list)-1:
                for j in range(count_minlist,len(min_list)):
                    if max_list[i] <= min_list[j]:
                        aux_list.append(max_list[i])
                        count_maxlist +=1
                        break
                    else:
                        aux_list.append(min_list[j])
                        count_minlist +=1
            else:
                break

        while count_maxlist <= len(max_list) -1:
            aux_list.append(max_list[count_maxlist])
            count_maxlist += 1

        while count_minlist <= len(min_list) -1:
            aux_list.append(min_list[count_minlist])
            count_minlist += 1
        
        return aux_list
    else:
        return lista

Les recomiendo que coloquen un

breakpoint()

al inicio de la funci贸n de ordenamiento por mezcla, eso les ayudara para saber que pasa en cada l铆nea de c贸digo.

Una forma de verlo graficamente, la parte azul es la recursividad y la parte naranja donde se van ordenando las listas

Aporte

Tuve que borrar y escribir el algoritmo como 5 veces para entenderlo, al final lo lo logr茅鈥 les comparto mi c贸digo con anotaciones.

C贸digo

import random

def merge_sort(dataset):
    """Sorts a list of numbers using the Merge Sort algorithm.

    The original list will be mutated.

    Time Complexity: O(n log n)
    """
    dataset_len = len(dataset)

    # Se verifica si la lista proporcionada tiene m谩s de un elemento,
    # esto ser谩 la condici贸n que pare la recursi贸n dado que estamos basando
    # nuestra l贸gica en el principio de que una lista de 1 elemento es igual
    # a una lista ordenada.
    if dataset_len > 1:
        middle = dataset_len // 2
        # Ordenamos el lado izquiedo de la lista
        left = merge_sort(dataset[0:middle])
        
        # Ordenamos el lado derecho de la lista
        right = merge_sort(dataset[middle:])

        # Obtenemos el n煤mero de elementos en cada sub lista.
        # Solo lo guardamos en una variable por que se utiliza repetidamente
        # en las siguentes l铆neas.
        left_len = len(left)
        right_len = len(right)

        # Sub nodes iterators

        # Definimos unas banderas de iteraci贸n que nos ayudar谩n a recorrer los 铆ndices de cada sub-lista (Izquierda y derecha)
        left_idx = 0
        right_idx = 0
        
        # Iterator of the main list

        # Definimos una bandera de iteraci贸n que nos ayudar谩 a recorrer nuestra lista principal
        index = 0


        # Este ciclo lo que har谩 es unir (Merge) las dos listas generadas, con la condici贸n
        # de que los 铆ndices no sobre pasen el n煤mero de elementos de su lista respectiva.
        # 
        # Esto significa que puede llegar el caso en el que la longitud de las 2 listas sea diferente
        # y una de las 2 listas se termine de unir a la lista principal primero. 
        while left_idx < left_len and right_idx < right_len:
            
            # Revisamos en qu茅 lista est谩 el valor m谩s peque帽o y lo unimos a la lista principal
            if left[left_idx] < right[right_idx]:

                # Si el valor m谩s peque帽o estaba en la lista izquierda lo a帽adimos a la lista principal
                # e incrementamos el 铆ndice izquierdo para no re-evaluar el mismo valor en la iteraci贸n siguiente.
                dataset[index] = left[left_idx]
                left_idx += 1
            else:
                # Si el valor m谩s peque帽o estaba en la lista derecha lo a帽adimos a la lista principal
                # e incrementamos el 铆ndice derecho para no re-evaluar el mismo valor en la iteraci贸n siguiente.
                dataset[index] = right[right_idx]
                right_idx += 1
            
            # Incrementamos el 铆ndice de la lista principal indicando que el valor colocado en esa posici贸n
            # ya est谩 ordenado.
            index += 1

        # Una vez llegado a este paso nuestra lista principal ya est谩 casi completamente ordenada,
        # pero como comentamos anteriormente, es posible que una de las 2 listas sea m谩s grande
        # que la otra, por lo pueden existir n煤meros de una de las 2 listas que no hayamos unido a 
        # la lista principal.
        # 
        # Es importante tener en cuenta que aunque a continuaci贸n se recorren las 2 listas, es imposible
        # que se ejecuten los 2 ciclos, dado que solo puede haber sobrado n煤meros en una de las 2 sub-listas
        # y la raz贸n de que est茅n los 2 ciclos (uno para cada sub-lista) es que no sabes a cu谩l le sobraron
        # n煤meros y dado el comportamiento del ciclo while solo se ejecutar谩 aqu茅l ciclo cuya lista tenga
        # sobrantes y se a帽adir谩n al final de la lista principal.
        while left_idx < left_len:
            dataset[index] = left[left_idx]
            left_idx += 1
            index += 1
        
        while right_idx < right_len:
            dataset[index] = right[right_idx]
            right_idx += 1
            index += 1

    return dataset


if __name__ == '__main__':
    list_size = int(input('驴De qu茅 tama帽o ser谩 la lista?'))

    dataset = [random.randint(0, 100) for i in range(0, list_size)]

    print('Unsorted list', dataset)
    merge_sort(dataset)
    print('=' * 15)
    print('Sorted list', dataset)

No comprend铆 joder c:

Comunidad, he agregado varios print statements para que se vea qu茅 ejecuta el sistema paso a paso y as铆 poder entender bien el ordenamiento por mezcla. Espero les sirva y si ven alguna mejora que se pueda hacer, me avisan.

import random

def ordenamiento_por_mezcla(lista):
if len(lista) > 1:
medio = len(lista) // 2 #divido entre 2 el tama帽o de la lista. Con esto podr茅 indicar los l铆mites de 2 sublistas
izquierda = lista[:medio] #divido la lista desde el inicio hasta el valor del medio
derecha = lista[medio:] # y desde el valor del medio hasta el final
print(izquierda, 鈥*鈥 * 5, derecha) # imprimo las 2 sub listas

    #realizo la recursividad de tal forma que cada vez se vayan dividiendo
    #las listas entre 2 hasta que cada valor quede de forma independiente
    #esto lo realizo para las sublista de la izquierda y derecha
    ordenamiento_por_mezcla(izquierda)
    ordenamiento_por_mezcla(derecha)

    #Tengo que recorrer las listas para comparar los valores y ordenar
    #para esto creo 2 iteradores
    i = 0
    j = 0
    #asimismo, creo un tercer iterador para recorrer la lista principal
    #en donde se alojar谩n los valores ordenados poco a poco
    k = 0
    
    while i < len(izquierda) and j < len(derecha):
        #si el primer valor de la sublista izquierda es menor que el 
        #primer valor de la sublista derecha, entonces
        print(i, "<", len(izquierda), " y ", j, "<", len(derecha), "?")
        if izquierda[i] < derecha[j]:
            print("S铆, entonces :", izquierda[i], "<", derecha[j], "?")
            #la lista en la primera posici贸n, tomar谩 el valor de izquierda
            lista[k] = izquierda[i]
            print("si,", izquierda[i], "se agrega a la lista")
            #le sumo 1 para ir a la siguiente posici贸n dentro de la sublista izquierda
            i += 1
            print("incrementamos en 1 el valor de i")
        else:
            print(izquierda[i], "<", derecha[j], "?")
            #caso contrario, la lista en su primera posici贸n
            #asumir谩 el valor de la sublista derecha en su primera posici贸n
            lista[k] = derecha[j]
            print("No, entonces ", derecha[j], "se agrega a la lista")
            j += 1
            print("incrementamos en 1 el valor de j")
        print("incrementamos en 1 el valor de k")
        k += 1
        print("i=", i, "j=", j, "k=", k)
    while i < len(izquierda):
        print(i, "<", len(izquierda))
        lista[k] = izquierda[i]
        print(izquierda[i], "se agrega a la lista")
        i += 1
        k += 1
    
    while j < len(derecha):
        print(j, "<", len(derecha))
        print(derecha[j], "se agrega a la lista")
        lista[k] = derecha[j]
        j += 1
        k += 1
    
    print(f"izquierda {izquierda}, derecha {derecha}")
    print("la lista queda de la siguiente forma: ", lista)
    print("-" * 50)

    return lista

if name == 鈥main鈥:
#defino el tama帽o de la lista
tamano_lista = int(input(鈥淚ngrese el tama帽o de la lista: 鈥))
#asigno valores aleatorios de acuerdo al tama帽o de la lista ingresado
lista = [random.randint(0, 100) for i in range(tamano_lista)]
#imprimo los valores de la lista
print(lista)
print(鈥*鈥 * 50)

#llamo a una funci贸n que ordene la lista.
#En este caso, el ordenamiento se realizara con el metodo de mezcla
#le doy como parametro la lista previamente creada con valores aleatorios
lista_ordenada = ordenamiento_por_mezcla(lista)
#imprimo la lista ordenada
print(lista_ordenada)

Tuve un problema con el c贸digo del profesor respecto a las variables izquierda y derecha que se declaran dentro del if, me tiraba el error 鈥淯nboundLocalError: local variable 鈥榠zquierda鈥 referenced before assignment鈥, las saqu茅 del if y las puse antes, de modo que su alcance sea en toda la funci贸n, y ah铆 si anduvo todo perfecto.

Algoritmo de ordenamiento r谩pido o quicksort:

Les dejo esta implementaci贸n hecha en Python, fue bastante complejo entender como funciona y justamente donde realizar el llamado de la recursividad pero vale la pena.

import random

def ordenamiento_rapido(lista, izq, der):

    if izq < der:
        pivote = lista[izq] #Inicialmente toma el valor de la posici贸n 0, a medida q se va aplicando la recursividad
                            #obtiene un nuevo valor pivote de acuerdo a la posici贸n.
        i = izq             #Inicializaci贸n de indices i y j para luego recorrer la lista de der a izq y de izq a der
        j = der        
        while ( i < j ):
            while ( lista[i] < pivote ): #Mientras el valor que tiene en esa posici贸n i es menor q pivote incrementa su valor, es decir no debe realizar
                                         #intercambio
                i+=1
            while lista[j] > pivote:     #Mientras el valor que tiene en esa posici贸n j es mayor que pivote incrementa su valor, es decir no debe realizar
                                         #intercambio
                j-=1
            if i < j:                   
                temp = lista[i]          #se declara un objeto temporal para hacer el intercambio de posiciones
                lista[i] = lista[j]
                lista[j] = temp

        ordenamiento_rapido(lista, izq, j-1) #Llamado recursivo lista menor que pivote, posicion inicial hasta la posici贸n del pivote - 1
        ordenamiento_rapido(lista, i+1, der) #Llamado recursivo lista mayor que pivote, posicion pivote + 1 hasta el final de la lista

    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)]
#    lista = [8, 4, 9, 3, 5, 7, 1, 6, 2]
    print(f'Lista inicial en desorden: {lista}')

    lista_ordenada = ordenamiento_rapido(lista, 0, len(lista)-1)
    print(f'Lista en orden: {lista_ordenada}')

despu茅s de un buen rato le entend铆

import random


def ordenamiento_por_mezcla(lista):
    if len(lista) > 1: #Longitud de la lsita es mayor a 1 ---> Ya hicios la lista suficientemente peque帽a
        #no ejecuta nada porque significa que ya esta completo
        medio = len(lista) // 2 #primero debemos encontrar la mitad

        izquierda = lista[:medio] # lista de 0 hasta la mitad
        derecha = lista[medio:] # lista de la mitad hasta el final ### NOTACION DE REBANADA
        print(izquierda, "*" * 5, derecha)
        #Llamada recursiva en cada mitad
        ordenamiento_por_mezcla(izquierda)
        ordenamiento_por_mezcla(derecha)
        #Crecimiento logaritmico

        #Crear 2 iteradores para recorrer las 2 sublistas
        i = 0
        j = 0
        k = 0 #Sirve para iterar en la lista principal

        #comparaciones 
        while i < len(izquierda) and j < len(derecha): #Si se cumplen estas 2 condiciones podremos seguir comparando
            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(i)
        print(j)
        print(k)
        print("_" * 5)
        
    return lista


if __name__ == "__main__":
    tamano_de_lista = int(input("驴Que cantidad de datos tendra la lista?: "))

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

    lista_organizada = ordenamiento_por_mezcla(lista)
    print(lista_organizada)

ganan en tiempo, pero pierde en memoria

No lo voy a negar me costo un poco repet铆 el v铆deo como 20 veces pero me quedo claro lo que me quedo un poco en el aire es los 2 煤ltimos wile se que es para que copien los elementos que faltan pero el j += 1 y el i +=1 no entiendo como detienen el loop pero me gusto la menara en que funciona el ordenamiento por mezcla dividiendo la lista hasta que quede 1 elemento y luego rearmando la ordenada.

Este me cost贸, pens茅 que estaba entendiendo recursividad pero pregunto: Los ciclos while no se ejecutan sino hasta que solo se tenga lista de 1 elementos?

Me cost贸 entenderlo, pero si vas revisando paso a paso, te vas dando cuenta como va siendo el proceso.

Que c贸digo tan interesante, me gusto mucho la clase

https://jarednielsen.com/big-o-logarithmic-time-complexity/ Encontr茅 est谩 p谩gina que explica la complejidad logar铆tmica, est谩 en ingl茅s y el ejemplo es con js, pero no la descarten. Es simplemente genial, tanto el lenguaje como los ejemplos y explicaciones que usan son muy simples.

MergeSort siempre tiene O(n log n) de tiempo, pero puede mejorarse el espacio utilizado. En la implementaci贸n que se muestra en la clase estamos usando O(n log n) de espacio en memoria.

Aqu铆 les dejo otra implementaci贸n que solo crece O(n) de espacio, pues solamente crea un array auxiliar en vez de dividir el original. Adem谩s hace la mutaci贸n in situ.
Ojal谩 les guste:

def mergeSort(array):
    if len(array) <= 1:
		return array
	auxiliaryArray = array[:]
	mergeSortHelper(array, 0, len(array) - 1, auxiliaryArray)
	return array
		
def mergeSortHelper(mainArray, startIdx, endIdx, auxiliaryArray):
	if startIdx == endIdx:
		return
	middleIdx = (startIdx + endIdx) // 2
	mergeSortHelper(auxiliaryArray, startIdx, middleIdx, mainArray)
	mergeSortHelper(auxiliaryArray, middleIdx + 1, endIdx, mainArray)
	doMerge(mainArray, startIdx, middleIdx, endIdx, auxiliaryArray)
	
def doMerge(mainArray, startIdx, middleIdx, endIdx, auxiliaryArray):
	k = startIdx
	i = startIdx
	j = middleIdx + 1
	while i <= middleIdx and j <= endIdx:
		if auxiliaryArray[i] <= auxiliaryArray[j]:
			mainArray[k] = auxiliaryArray[i]
			i += 1
		else:
			mainArray[k] = auxiliaryArray[j]
			j += 1
		k += 1
		
	while i <= middleIdx:
		mainArray[k] = auxiliaryArray[i]
		i += 1
		k += 1
		
	while j <= endIdx:
		mainArray[k] = auxiliaryArray[j]
		j += 1
		k += 1

Me encanta la cara de David cuando empieza a explicar el algoritmo, su sonrisa y emoci贸n me record贸 a m铆 haciendo mi trabajo, disfruta hablando de estos temas y tambi茅n inspira a seguir aprendiendo.

alguien me explica bien la funcion del primer while que usamos

No entiendo cuando se deja de ejecutar la recursividad!

def ordenamiento_por_mezcla(lista):
  if len(lista) > 1:
    medio = len(lista) // 2
    izquierda = lista[:medio]
    derecha = lista[medio:]
    print(f'dividiendo izquierda: {izquierda} derecha {derecha}')

    # llamada recursiva en cada mitad
    ordenamiento_por_mezcla(izquierda)
    ordenamiento_por_mezcla(derecha)
    print('y esto pa cuando')

    # Iteradores para recorrer las dos sublistas
    i = 0
    j = 0
    # Iterador para la lista principal
    k = 0```
El c贸digo me funciona, pero no logro entender porqu茅 se deja de ejecutar la recursividad y empieza a comparar! 

Para el que a煤n no entendi贸, como yo hace 2 d铆as, les dejo el c贸digo con los print statements en cada paso para que vena qu茅 es lo que hace el sistema. Espero sea de ayuda. Un abrazo

import random

def ordenamiento_por_mezcla(lista):
if len(lista) > 1:
medio = len(lista) // 2 #divido entre 2 el tama帽o de la lista. Con esto podr茅 indicar los l铆mites de 2 sublistas
izquierda = lista[:medio] #divido la lista desde el inicio hasta el valor del medio
derecha = lista[medio:] # y desde el valor del medio hasta el final
print(izquierda, 鈥*鈥 * 5, derecha) # imprimo las 2 sub listas

    #realizo la recursividad de tal forma que cada vez se vayan dividiendo
    #las listas entre 2 hasta que cada valor quede de forma independiente
    #esto lo realizo para las sublista de la izquierda y derecha
    ordenamiento_por_mezcla(izquierda)
    ordenamiento_por_mezcla(derecha)

    #Tengo que recorrer las listas para comparar los valores y ordenar
    #para esto creo 2 iteradores
    i = 0
    j = 0
    #asimismo, creo un tercer iterador para recorrer la lista principal
    #en donde se alojar谩n los valores ordenados poco a poco
    k = 0
    
    while i < len(izquierda) and j < len(derecha):
        #si el primer valor de la sublista izquierda es menor que el 
        #primer valor de la sublista derecha, entonces
        print(i, "<", len(izquierda), " y ", j, "<", len(derecha), "?")
        if izquierda[i] < derecha[j]:
            print("S铆, entonces :", izquierda[i], "<", derecha[j], "?")
            #la lista en la primera posici贸n, tomar谩 el valor de izquierda
            lista[k] = izquierda[i]
            print("si,", izquierda[i], "se agrega a la lista")
            #le sumo 1 para ir a la siguiente posici贸n dentro de la sublista izquierda
            i += 1
            print("incrementamos en 1 el valor de i")
        else:
            print(izquierda[i], "<", derecha[j], "?")
            #caso contrario, la lista en su primera posici贸n
            #asumir谩 el valor de la sublista derecha en su primera posici贸n
            lista[k] = derecha[j]
            print("No, entonces ", derecha[j], "se agrega a la lista")
            j += 1
            print("incrementamos en 1 el valor de j")
        print("incrementamos en 1 el valor de k")
        k += 1
        print("i=", i, "j=", j, "k=", k)
    while i < len(izquierda):
        print(i, "<", len(izquierda))
        lista[k] = izquierda[i]
        print(izquierda[i], "se agrega a la lista")
        i += 1
        k += 1
    
    while j < len(derecha):
        print(j, "<", len(derecha))
        print(derecha[j], "se agrega a la lista")
        lista[k] = derecha[j]
        j += 1
        k += 1
    
    print(f"izquierda {izquierda}, derecha {derecha}")
    print("la lista queda de la siguiente forma: ", lista)
    print("-" * 50)

    return lista

if name == 鈥main鈥:
#defino el tama帽o de la lista
tamano_lista = int(input("Ingrese el tama帽o de la lista: "))
#asigno valores aleatorios de acuerdo al tama帽o de la lista ingresado
lista = [random.randint(0, 100) for i in range(tamano_lista)]

#imprimo los valores de la lista
print(lista)
print("*" * 50)

#llamo a una funci贸n que ordene la lista.
#En este caso, el ordenamiento se realizara con el metodo de mezcla
#le doy como parametro la lista previamente creada con valores aleatorios
lista_ordenada = ordenamiento_por_mezcla(lista)
#imprimo la lista ordenada
print(lista_ordenada)

Este video me ayudo mucho a ver gr谩ficamente como funciona la recursividad en el ejercicio. https://www.youtube.com/watch?v=nga05GPMsRs

Concuerdo que este algoritmo tiene una complejidad logar铆tmica. Ejecut茅 pruebas utilizando un Jupyter Notebook corriendo en Docker con 1 CPU.

10 Elementos (116 micro-segundos por loop)

3.1 ms 卤 116 碌s per loop (mean 卤 std. dev. of 7 runs, 100 loops each)

100 Elementos (530 micro-segundos por loop)

16.7 ms 卤 530 碌s per loop (mean 卤 std. dev. of 7 runs, 100 loops each)

1000 Elementos (3.74 mili-segundos por loop)

165 ms 卤 3.74 ms per loop (mean 卤 std. dev. of 7 runs, 10 loops each)

Si a alguien le est谩 costando como a mi entender bien el c贸digo le recomiendo lo siguiente (porque despu茅s de 1 hora literalmente leyendo y releyendo entend铆 jaja)

  • PRIMERO: Mira TODO el video de recorrido (a煤n si no entiendes la mayor铆a)
  • SEGUNDO: NO te fijes en la teor铆a que se muestra al principio de la clase, f铆jate mejor en lo que imprime el programa en el minuto 15:34 ya que ah铆 la teor铆a lo ves de mejor manera
  • TERCERO: Entiende la primera parte del c贸digo que dividide la lista desordenada en listas 鈥渙rdenada鈥 de un solo elemento
  • CUARTO: Copia a mano en un papel separado lo que est谩 en el minuto 15:34 y luego pon en la pantalla el c贸digo para que a medida que vayas leyendo el c贸digo vayas viendo lo que imprime
  • QUINTO: cae en cuenta que lo M脕S IMPORTANTE DE AQU脥 (por lo menos para mi cuando lo empec茅 a entender) Es el CONTEXTO DE EJECUCI脫N. si se dan cuenta, la primera ves que se imprime, todo ocurre literalmente en la l铆nea de c贸digo que dice 鈥渙rdenamiento_por_mezcla(izquierda)鈥 (piensen)
  • SEXTO: repasen el primer paso a lo largo del c贸digo y haganlo manualmente diciendo que pasa en cada una de las l铆neas.

Por lo menos as铆 me sirvi贸 a a mi =)

Claro como el chocolate espeso鈥 la verdad es que si se entiende luego de hacer los prints y ver el video explicativo del compa帽ero

Esto ser铆a como una propiedad asociativa, pero en vez de multiplicar comparo con mayor que. Se me eriz贸 la piel de ver como funcionaba

Explicaci贸n gr谩fica de los pasos:

Hola! Con este diagrama y dejando expl铆cito por donde va el c贸digo me ayudo much铆simo. Dejo ambos. Saludos!

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
        print('empieza ordenamiento por mezcla izquierda')
        ordenamiento_por_mezcla(izquierda)
        print('termina ordenamiento por mezcla izquierda')
        print('empieza ordenamiento por mezcla derecha')
        ordenamiento_por_mezcla(derecha)
        print('termina 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):
            print(f'lista en primer ciclo while {lista}')
            print('entra a primer ciclo while')
            if izquierda[i] < derecha[j]:
                print('entra a if parte de primer ciclo while')
                lista[k] = izquierda[i]
                i += 1
                print(f'i={i}')
                print(f'lista k if en primer ciclo while: {lista}')
            else:
                print('entra a else de primer ciclo while')
                lista[k] = derecha[j]
                j += 1
                print(f'j={j}')
                print(f'lista k else de ciclo while: {lista}')

            k += 1
            print(f'k={k}')
            print(f'lista despu茅s de salir de primer ciclo while={lista}')
        while i < len(izquierda):
            print('segundo ciclo while')
            lista[k] = izquierda[i]
            i += 1
            k +=1
            print(f'i={i}')
            print(f'k={k}')
            print(f'lista k en segundo ciclo while: {lista}')

        while j < len(derecha):
            print('tercer ciclo while')
            lista[k] = derecha[j]
            j += 1
            k += 1
            print(f'j={j}')
            print(f'k={k}')
            print(f'lista k en tercer ciclo while: {lista}')
        
        print(f'izquierda {izquierda}, derecha {derecha}')
        print(lista)
        print('-' * 50)
    print('termina ciclo de if')
    return lista
print('termina funcion')

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('-' * 50)

    lista_ordenada = ordenamiento_por_mezcla(lista)
    print('termino')
    print(lista_ordenada)

Que buena clase!.

Esta clase me rompi贸 la cabeza jajaj. Muy buena!

Aqu铆 encontr茅 otra definici贸n y c贸digo f谩cil de comprender, espero le sirva. En este video tambi茅n hay un ejercicio para que repasen el c贸digo.

wow! No lo entend铆 jajajaja a buscar info :3

Hola equipo, me sirvi贸 mucho hacerle debug al c贸digo, que explica Facundo en el siguiente video:
https://platzi.com/clases/2255-python-intermedio/36469-debugging/

Me duele la cabeza pero por fin lo entend铆:
Les comparto los puntos claves que yo considero me ayudaron a comprenderlo.
Cuando realiza las llamadas recursivas por cada mitad estas funciones modifican las sublistas por lo que en teor铆a retornan el contenido de cada mitad ordenado, es decir, que cuando empiezan los ciclos estos reciben dos listas previamente ordenadas, empezando por el ultimo nivel donde las listas solo tienen un solo elemento, por otro lado, si se fijan en el primer ciclo while, en cada iteraci贸n solo uno de los iteradores de las sublistas se incrementa, por eso es necesario los otros whiles, que agregan lo que ya no se puede comparar pero que ya esta organizado.

Queriendo comprender como funciona este algoritmo, utilice la herramienta de VSC de Debbuging y puse breakpoints en todas las lineas del cuerpo de la funci贸n recursiva ordenamiento_por_mezcla() para ver como las variables locales (lista, medio, izquierda y derecha) iban modificando su valor en cada recursion, Me llamo mucho la atenci贸n que estas variables locales (recuerdan) el valor de la recursion anterior, Asi que busque en internet como se comportan las variable locales en funciones repulsivas y me encontr茅 esto:

El orden inverso de ejecuci贸n es una caracter铆stica t铆pica de todas las funciones recursivas. Si una funci贸n recursiva tiene variables locales, se crear谩 un conjunto diferente de variables locales durante cada nueva llamada. Los nombres de las variables locales ser谩n los mismos, como los hallamos declarado en la funci贸n. Sin embargo, las variables representar谩n un conjunto diferente de valores cada vez que se ejecute la funci贸n. Cada conjunto de valores se almacenar谩 en la pila, as铆 cuando el proceso recursivo se deshaga (cuando las llamadas a la funci贸n se saquen de la pila y sigan su ejecuci贸n) podremos disponer de ellas.

https://ccia.ugr.es/~jfv/ed1/c/cdrom/cap6/cap66.htm

Lo comparto por ac谩 por si le ayuda a alguien mas a comprender la recursividad, a mi me pareci贸 super interesante.

Qu茅 algoritmo tan brutal! Me orden贸 1 MILL脫N de n煤meros en tan solo 20 segundos! 馃ザ

Algo que me ayud贸 a entender el c贸digo fue, que en python, los par谩metros son referencia.

馃摙Peque帽os aportes que (quiz谩) te ahorraran tiempo :

  1. Recuerda que las listas al ser modificadas en una funci贸n son modificadas en su instancia original

  2. Usa el debugger de VScode y presta atenci贸n a las variables izquierda y derecha, adem谩s del desarrollo del ordenamiento

  3. Si sabes ingles este video te aclarar谩 muchas dudas.

  4. Este video en espa帽ol tambi茅n puede ayudarte

  5. La parte de los iteradores yo lo entend铆 como:
    - Ya analizamos este elemento ( i = 0 \ j =0 ) pasemos al siguiente( i +=1 \ j += 1)
    - Estoy ordenando este elemento ( k = 0 ) ahora ordenamos este ( k += 1 )

  6. Nota mental : Repasa ma帽ana que probablemente se te olvide lo poco que entendiste 馃槪馃槬

猸愶笍猸愶笍猸愶笍Divide y conquista.猸愶笍猸愶笍猸愶笍

El ordenamiento por mezcla creado por John von Neumann el cual aplica el concepto de 鈥渄ivide y conquista鈥. Primero divide una lista en partes iguales hasta que quedan sublistas de 1 o 0 elementos. Luego las recombina en forma ordenada.

El profesor viendo como intentas entender su algoritmo.


Pd: Llevo horas aun no entiendo a detalle el codigo.

Entendia como funciona el ordenamiento pro mezcla pero no entendia como funcionaba el programa en python.

solo con la opcion 鈥渞un and debug鈥 y ver paso por paso como funciona el programa pude entender lo que hacia el codigo

Esta super complejo este tipo de ordenamiento pero comparto lo que yo entendi del algoritmo que se planteo:

lista = [75, 74, 32, 83, 99, 14, 47, 61, 82, 19]

1 .- Recibe la lista y las divide a la mitad,
[75, 74, 32, 83, 99] ***** [14, 47, 61, 82, 19]
2.- crea un una lista nueva con toda la informaci贸n medio a la izquierda lista[:medio] [75, 74, 32, 83, 99]
3.- crea un una lista nueva con toda la informaci贸n medio a la derecha lista[medio:] [14, 47, 61, 82, 19]
4.- Luego mediante recursividad le pasa la lista de la izquierda, repitiendo el paso 1, 2 y 3.
[75, 74, 32, 83, 99], paso 1, 2 y 3 [75, 74] ***** [32, 83, 99],
5 .- se queda con la lista mas peque帽a y le aplica la comparaci贸n para ordenarlos. [74, 75]
6.- luego la lista de la derecha [32, 83, 99] le aplica el paso 1,2 y 3 [32] ***** [83, 99] y luego le aplica el paso 5 nuevamente [83, 99] y los ordena [83, 99] en este caso los deja igual
7.- ya al final los empieza a unir comparandolos nuevamente [32, 74, 75, 83, 99] hasta devolverlos ordenados

MultiFrames!!!

llevo mas de 24 leyendo, modificando y tratando de comprender esto c贸digo, hasta ahora lo que me ha resultado mas 煤til es debugearlo paso a paso.

al principio me costaba comprender porque el c贸digo se segu铆a ejecutando aun despu茅s de llegar a la l铆nea final y ahora comienzo a comprender como y cuando se generan los diferentes frames me doy cuenta que es la l铆nea de ese frame en particular y que cada vez que eso sucede ( llegar a la l铆nea final, que sucede una vez alcanzado el caso base ), la ejecuci贸n desciende al frame anterior , donde todo el c贸digo se ejecuta nuevamente

La explicaci贸n la da el profesor a partir del minuto 17:52, lo interesante es interiorizar el concepto!

tuve que ver el video varias veces 馃く

Lo termin茅 de entender perfectamente con este video

Recomiendo usar el debugger de vscode para ir paso a paso y entender mejor el algoritmo. Tambi茅n tener en cuenta que el c贸digo del profesor est谩 mutando la lista original lo que lo hace un poco m谩s dif铆cil de entender.

Aqu铆 dejo una versi贸n que no muta la lista original por si les ayuda:

import random

def ordenamiento_por_mezcla(lista):
    sorted_list = lista[:] # copiar la lista
    if len(sorted_list) > 1:
        medio = len(sorted_list) // 2
        izquierda = sorted_list[:medio]
        derecha = sorted_list[medio:]
        print(izquierda, '*' * 5, derecha)

        # llamada recursiva en cada mitad
        izquierda = ordenamiento_por_mezcla(izquierda) # obtener lista ordenada
        derecha = ordenamiento_por_mezcla(derecha) # obtener lista ordenada

        # 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]:
                sorted_list[k] = izquierda[i]
                i += 1
            else:
                sorted_list[k] = derecha[j]
                j += 1

            k += 1

        while i < len(izquierda):
            sorted_list[k] = izquierda[i]
            i += 1
            k +=1

        while j < len(derecha):
            sorted_list[k] = derecha[j]
            j += 1
            k += 1
        
        print(f'izquierda {izquierda}, derecha {derecha}')
        print(sorted_list)
        print('-' * 50)

    return sorted_list


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)

Sigo recomendando este enlace, tiene todos los tipos de ordenamiento con codigo y paso a paso
https://visualgo.net/es/sorting

John von Neumann

Si no entienden el c贸digo, puede ser porque no comprenden la recursividad, aqu铆 un video que la explica a la perfecci贸n: https://www.youtube.com/watch?v=0NBPd81uhJE

Algo que a mi me ayudo mucho a entender mejor el proceso del algoritmo fue debuggearlo, asi pude ir viendo paso a paso que es lo que iba sucediendo. recomiendo mucho Vs code para debuggear ya que la herramienta que trae es muy intuitiva.

Tre mendo, yo solo tengo una pregunta: 驴Qu茅 estaba pensando la persona que creo esto?

馃挕 Partiendo del c贸digo presentado en clase, hice una versi贸n donde solo se necesita un while (siendo un algoritmo mas eficiente), menos lineas de c贸digo, y a mi parecer puede ser un poco m谩s entendible.

Aca esta el repositorio en GitHub con los dos archivos de cada version: La version de la calse (en ingles) y la version mejorada
https://github.com/Giosorio/merge_sort

tambi茅n dejo el c贸digo en la version espa帽ol:

import random 

def ordenamiendo_por_mezcla(lista):
    if len(lista) > 1:
        medio = len(lista)//2
        izquierda = lista[:medio]
        derecha = lista[medio:]
        
        # Print the process 
        # print(izquierda, '*' * 5, derecha)

        # Llamada recursiva en cada mitad
        izquierda = ordenamiendo_por_mezcla(izquierda)
        derecha = ordenamiendo_por_mezcla(derecha)

        
        lista = []
        while len(izquierda) != 0 and len(derecha) != 0:
            if izquierda[0] < derecha[0]:
                lista.append(izquierda.pop(0))
            else:
                lista.append(derecha.pop(0))


        if len(izquierda) > 0:
            lista += izquierda
        else:
            lista += derecha
        
        
        # Print the process 
        # print('izquierda {}, derecha {}'.format(izquierda, derecha))
        # print(lista)
        # print('-' * 5)

    return lista 




if __name__ == '__main__':
    tamano_de_lista = int(input('Tamano de lista: '))

    lista = [random.randint(0, 100) for i in range(tamano_de_lista)]
    # lista = [3, 41, 11, 84, 25]
    print(lista)
    print('-' * 5)

    lista_ordenada = ordenamiendo_por_mezcla(lista)
    print(lista_ordenada)

el merge sort, es n log n

El hecho de dividir dentro del proceso de un algoritmo, hace que este tenga una notaci贸n de log de n.

El merge sort, lo invent贸 Jhon Vonn Numann.

Lo que hacemos en el merge sort, es dividir al punto m铆nimo la lista, en una lista de longitud 1, por lo que apartir de ah铆 podemos empezar a comparar hasta llegar a la lista completamente ordenada.

Nuevamente, uno de los algoritmos m谩s poderosos, utilizan la estrategia de divide y conquista.