Ordenar por fusión en Python

1. Utilice la recursividad para implementar la ordenación por fusión en Python
2. Use la ordenación de combinación iterativa en Python

Merge sort es un algoritmo de clasificación popular que se utiliza para clasificar los elementos de cualquier estructura de datos dada. Este tutorial analiza el algoritmo de clasificación por fusión y cómo implementarlo en Python.

Merge sort es un excelente ejemplo del enfoque divide y vencerás y se utiliza para clasificar grandes conjuntos de datos. El algoritmo comienza dividiendo la estructura de datos dada en dos partes y luego repite el mismo proceso en ambas mitades. Finalmente, combina las mitades para obtener valores ordenados de manera eficiente. Por lo tanto, lo llamamos un excelente ejemplo del enfoque de divide y vencerás.

La mejor parte de este algoritmo es que tiene una complejidad de tiempo consistente de O(nlogn) en los tres casos posibles (caso promedio, mejor caso y peor caso). Debido a este hecho, generalmente se considera eficiente y se prefiere para grandes conjuntos de datos.

Ahora veremos cómo implementar el algoritmo de clasificación por fusión usando el lenguaje de programación Python.

Utilice la recursividad para implementar la ordenación por fusión en Python

La ordenación por combinación se implementa simplemente en Python con la ayuda de una función recursiva.

El siguiente código usa la recursividad para implementar la ordenación por fusión en Python.

def m(left, right):
    if not len(left) or not len(right):
        return left or right

    result = []
    i, j = 0, 0
    while len(result) < len(left) + len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
        if i == len(left) or j == len(right):
            result.extend(left[i:] or right[j:])
            break

    return result


def msort(list):
    if len(list) < 2:
        return list

    middle = int(len(list) / 2)
    left = msort(list[:middle])
    right = msort(list[middle:])

    return m(left, right)


lst = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(lst)
print("\n")
print("Sorted List:")
print(msort(lst))

El código anterior proporciona el siguiente resultado:

Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]

Explicación del código:

• La lista dada se separa en dos mitades, izquierda y derecha en cada llamada recursiva siempre que no se obtengan dos valores adyacentes.
• La función m() se crea y utiliza para fusionar las dos mitades que originalmente se dividieron en el primer paso.
• La función msort() realiza la mayor parte de la división y clasificación de la lista dada en el programa.

Use la ordenación de combinación iterativa en Python

El algoritmo iterativo de clasificación por combinación es un poco diferente del método recursivo general, ya que el primero utiliza el enfoque de abajo hacia arriba mientras que el segundo usa el enfoque de arriba hacia abajo. Sin embargo, la complejidad del tiempo y la respuesta final siguen siendo exactamente las mismas en ambos métodos.

Además, el método recursivo de clasificación por fusión hace uso de una pila auxiliar explícita, mientras que no es necesario en la implementación iterativa del algoritmo de clasificación por fusión.

El siguiente código usa el algoritmo iterativo de clasificación por fusión para implementar la clasificación por fusión en Python.

def msort(a):
    width = 1
    n = len(a)
    while width < n:
        l = 0
        while l < n:
            r = min(l + (width * 2 - 1), n - 1)
            m = (l + r) // 2
            if width > n // 2:
                m = r - (n % width)
            mer(a, l, m, r)
            l += width * 2
        width *= 2
    return a


def mer(a, l, m, r):
    n1 = m - l + 1
    n2 = r - m
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = a[l + i]
    for i in range(0, n2):
        R[i] = a[m + i + 1]

    i, j, k = 0, 0, l
    while i < n1 and j < n2:
        if L[i] > R[j]:
            a[k] = R[j]
            j += 1
        else:
            a[k] = L[i]
            i += 1
        k += 1

    while i < n1:
        a[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        a[k] = R[j]
        j += 1
        k += 1


a = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(a)
msort(a)
print("Sorted List:")
print(a)

El código anterior proporciona el siguiente resultado:

Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]

Desventajas de Merge Sort

Aunque la ordenación por combinación es muy popular y se considera muy eficiente, tiene algunos inconvenientes en varios casos, que se mencionan a continuación.

• Cuando se trata de un conjunto más pequeño de estructuras de datos, puede ser comparativamente más lento que los otros algoritmos de clasificación disponibles.
• Se necesita espacio de memoria adicional para implementar este algoritmo.
• El algoritmo siempre realizará todo el proceso, incluso cuando la estructura de datos dada ya esté ordenada.