Merge Sort - Algoritmo desglosado

14935

Hola a todos. En este artículo quiero explorar un poco cómo funciona el algoritmo de Merge Sort, Ordenamiento por Mezcla. Es el análisis del algoritmo implementado por profe David con un ejemplo. Si tienes dudas en el tema recursividad tal vez este ejemplo te pueda ayudar.

Comencemos

Supongamos un ejemplo sencillo, un arreglo no ordenado de 4 números.

[ 53, 28, 5, 48 ]

Nuestro programa hace la primera llamada:

lista = [53, 28, 5, 48]
ordenamiento_por_mezcla(lista)

Nuestro código es el siguiente:

defordenamiento_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 de la lista principal
        k = 0while i < len(izquierda) and j < len(derecha):
            if izquierda[i] < derecha[j]:
                lista[k] = izquierda[i]
                i += 1else:
                lista[k] = derecha[j]
                j += 1k += 1while i < len(izquierda):
            lista[k] = izquierda[i]
            i += 1k += 1

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

    return lista

Si el tamaño de la lista es mayor a 1, entra al if, de otra manera la función no hace en absoluto nada. El tamaño es 4, entonces en el primer segmento de código se tienen estos resultados:

medio = 2izquierda = [53, 28]
derecha = [5, 48]

Lo siguiente que tendremos será:

 ordenamiento_por_mezcla(izquierda)
 ordenamiento_por_mezcla(derecha)

Dos llamados a la misma función para cada sublista.

Recursividad

Antes de continuar, a vuelo de pájaro este será el esquema en que las funciones recursivas se llamaran. Cada vez que una ejecución llama a su vez la misma función, entramos a esta función nueva y hasta no terminarla no se continua con el resto de código. En total la función se llama 7 veces:

Segundo Llamado

La lista del segundo llamado es:

[ 53, 28 ]

Y el código nos deja estos resultados:

# RESULTADOSmedio = 1izquierda = [53]
derecha = [28]

Dónde acto seguido hará dos llamados nuevos:

ordenamiento_por_mezcla(izquierda) # Tercer llamado
ordenamiento_por_mezcla(derecha) # Cuarto llamado

Tercer Llamado

La lista del tercer llamado es:

[ 53 ]

Dado que la lista tiene 1 elemento, la función no entra al if. Y en memoria se tendrá que la variable izquierda contiene al 53 únicamente.

Resultado: [ 53 ]

Cuarto Llamado

La lista del cuarto llamado es:

[ 28 ]

De igual manera la lista tiene 1 elemento y la función no entra al if. En memoria se tendrá que la variable derecha contiene al 28 únicamente.

Resultado: [ 53 ]

Continuación segundo llamado

Posteriormente tenemos los tres ciclos y sus índices:

# Iteradores para recorrer las dos sublistas
i = 0; j = 0
# Iterador de la lista principal
k = 0while i < len(izquierda) and j < len(derecha):
    if izquierda[i] < derecha[j]:
        lista[k] = izquierda[i]
        i += 1else:
        lista[k] = derecha[j]
        j += 1k += 1while i < len(izquierda):
    lista[k] = izquierda[i]
    i += 1k += 1

whilej < len(derecha):
    lista[k] = derecha[j]
    j += 1k += 1

Primer ciclo While

La función del primer ciclo while es comparar los elementos de la sublista izquierda y la sublista derecha uno a uno, ver cual es menor y guardarlos en la variable lista, que es nuestra lista principal.

Es decir mezcla dos sublistas que ya están ordenadas, y las guarda de manera ordenada. Este sería el caso más básico, dónde las dos sublistas constan de un elemento. Este primer ciclo solo tiene que comparar 53 y 28. El ciclo para cuando ya haya recorrido cualquiera de las dos sublistas en su totalidad.

# RESULTADOS# Antes del cicloi = 0; j = 0; k = 0
izquierda[0] = 53; derecha[0] = 28
...
# Después 1 Iteración del ciclo
lista[0] = 28j = 1; k = 1
...
# Total iteraciones: 1

Comparó, guardó el menor (derecha[0]) en el primer espacio de la lista principal, y el índice k queda en 1, dado que en 0 ya se ocupó el espacio.

j = 1 dado que ya recorrió el único elemento de derecha, y ya lo guardó. Pero quedó pendiente el de izquierda.

Segundo ciclo While

Este ciclo está hecho para la sublista izquierda.. Si después de comparar cada elemento, quedan elementos de izquierda que no se guardaron en lista, este ciclo los termina de guardar con el orden que tenían.

En nuestro caso se ejecuta y se tiene:

# RESULTADOS# Antes del cicloi = 0; j = 1; k = 1
...
# Después 1 Iteración del ciclo
lista[1] = 28i = 1; k = 2
...
# Total iteraciones: 1

Tercer ciclo While

Este ciclo hace lo mismo que el segundo, pero para la sublista derecha.

Nota: Dado que el primer ciclo recorre una de las dos listas en su totalidad, siempre va a quedar un remanente en la otra lista. Por ello, cuando se ejecuta el segundo ciclo, no se ejecutaría el tercero, o viceversa.

Finalmente, el parámetro de entrada del segundo llamado, lista, queda ordenado y aunque la última línea de código la retorna, ya esa variable que tenía números desordenados inicialmente queda modificada con los números ordenados. Es decir, podrías no retornar la lista y usar la variable de entrada.

Resultado: [ 28, 53 ]

Quinto Llamado

La lista del quinto llamado es:

[ 5, 48 ]

Y el código nos deja estos resultados:

# RESULTADOSmedio = 1izquierda = [5]
derecha = [48]

Dónde acto seguido hará dos llamados nuevos:

ordenamiento_por_mezcla(izquierda) # Sexto llamadoordenamiento_por_mezcla(derecha) # Séptimo llamado

Se puede observar que es el mismo proceso del Segundo Llamado, sólo que con la otra mitad de la lista. En resumen se tiene:

Sexto Llamado

Resultado: [ 5 ]

Séptimo Llamado

Resultado: [ 48 ]

# RESULTADOS - Primer ciclo# Antes del cicloi = 0; j = 0; k = 0
izquierda[0] = 5; derecha[0] = 48
...
# Después 1 Iteración del ciclo
lista[0] = 5i = 1; k = 1
...
# Total iteraciones: 1

...

# RESULTADOS - Tercer ciclo# Antes del cicloi = 1; j = 0; k = 1
...
# Después 1 Iteración del ciclo
lista[1] = 28i = 1; k = 2
...
# Total iteraciones: 1
...

El resultado es el mismo que el de la entrada ya que estaba ordenado. Sin embargo se hacen todos los pasos de dividir en sublistas y volver a armar un arreglo nuevo ordenado.

Resultado: [ 5, 48 ]

Nota: Recuerda que cada arreglo lista, izquierda, derecha son diferentes para cada llamada de la función. Por ejemplo fíjate que el arreglo izquierda del llamado inicial es el arreglo lista para el Segundo Llamado.

Continuación Llamado principal

Dado que los dos llamados recursivos iniciales (Segundo Llamado y Quinto Llamado) se terminaron de ejecutar y dejaron ordenadas las listas izquierdo y derecha, queda mezclar las dos listas ordenadas que cada uno de ellos proporcionaron.

Primer ciclo

# RESULTADOS # Antes del cicloi = 0; j = 0; k = 0izquierda = [ 28, 53 ] ; derecha[ 5, 48 ]
...
# Después 1 Iteración del ciclo
lista[0] = 5i = 0; j = 1; k = 1# Después 2 Iteración del ciclo
lista[1] = 28i = 1; j = 1; k = 2# Después 3 Iteración del ciclo
lista[2] = 48i = 1; j = 2; k = 3
...
# Total iteraciones: 3

Segundo Ciclo

# RESULTADOS # Antes del cicloi = 1; j = 2; k = 3
...
# Después 1 Iteración del ciclo
lista[3] = 53i = 2; k = 4
...
# Total iteraciones: 1
...

Resultado: [ 5, 28, 48, 53]

Et voilá

Si tienes algún comentario, sugerencia o pregunta, es totalmente bienvenido. Gracias por llegar hasta acá, les deseo éxito en la carrera de Data Science 😃

hace 4 años