Trier par fusion en Python

1. Utiliser la récursivité pour implémenter le tri par fusion en Python
2. Utiliser le tri de fusion itératif en Python

Le tri par fusion est un algorithme de tri populaire utilisé pour trier les éléments d’une structure de données donnée. Ce tutoriel explique l’algorithme de tri par fusion et comment l’implémenter en Python.

Le tri par fusion est un excellent exemple de l’approche diviser pour régner et est utilisé pour trier de grands ensembles de données. L’algorithme commence par diviser la structure de données donnée en deux parties, puis répète le même processus sur les deux moitiés. Enfin, il combine les moitiés ensemble pour obtenir des valeurs triées efficacement. C’est pourquoi nous l’appelons un excellent exemple de l’approche diviser pour régner.

La meilleure partie de cet algorithme est qu’il a une complexité temporelle constante de O(nlogn) dans les trois cas possibles (cas moyen, meilleur cas et pire cas). De ce fait, il est généralement considéré comme efficace et préféré pour les grands ensembles de données.

Nous allons maintenant voir comment implémenter l’algorithme de tri par fusion en utilisant le langage de programmation Python.

Utiliser la récursivité pour implémenter le tri par fusion en Python

Le tri par fusion est simplement implémenté en Python à l’aide d’une fonction récursive.

Le code suivant utilise la récursivité pour implémenter le tri par fusion 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))

Le code ci-dessus fournit la sortie suivante :

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

Explication des codes :

• La liste donnée est séparée en deux moitiés, gauche et droite à chaque appel récursif tant que deux valeurs adjacentes ne sont pas obtenues.
• La fonction m() est créée et utilisée pour fusionner les deux moitiés initialement divisées lors de la première étape.
• La fonction msort() effectue la majeure partie de la division et du tri de la liste donnée dans le programme.

Utiliser le tri de fusion itératif en Python

L’algorithme de tri par fusion itératif est un peu différent de la méthode récursive générale car le premier utilise l’approche ascendante tandis que le second utilise l’approche de haut en bas. Cependant, la complexité temporelle et la réponse finale restent exactement les mêmes dans les deux méthodes.

De plus, la méthode de tri par fusion récursive utilise une pile auxiliaire explicite, alors qu’elle n’est pas nécessaire dans l’implémentation de l’algorithme de tri par fusion itératif.

Le code suivant utilise l’algorithme de tri par fusion itératif pour implémenter le tri par fusion 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)

Le code ci-dessus fournit la sortie suivante :

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

Inconvénients du tri par fusion

Même si le tri par fusion est très populaire et considéré comme très efficace, il présente certains inconvénients dans divers cas, qui sont mentionnés ci-dessous.

• Lorsqu’il s’agit d’un ensemble plus petit de structures de données, il peut être comparativement plus lent que les autres algorithmes de tri disponibles.
• Un espace mémoire supplémentaire est nécessaire pour implémenter cet algorithme.
• L’algorithme suivra toujours l’ensemble du processus, même lorsque la structure de données donnée est déjà triée.