Tri par fusion

8.1 Définition du tri par fusion

Le tri par fusion (Merge Sort) est un algorithme de tri efficace, stable et comparatif qui utilise l'approche "diviser pour régner" pour organiser les éléments. L'algorithme divise le tableau en deux moitiés, trie récursivement chaque moitié, puis fusionne les moitiés triées en un seul tableau trié.

Principe de fonctionnement :

Division :

• Divisez le tableau d'origine en deux pour obtenir deux sous-tableaux.
• Répétez le processus pour chaque sous-tableau jusqu'à ce que chaque sous-tableau soit un tableau à un seul élément (ou vide).

Fusion :

• Fusionnez deux sous-tableaux adjacents en un seul tableau trié.
• Répétez le processus de fusion jusqu'à obtenir un seul tableau trié.

Complexité temporelle et spatiale du tri par fusion

Complexité temporelle :

• Dans le pire des cas : O(n log n)
• Dans le cas moyen : O(n log n)
• Dans le meilleur des cas : O(n log n)

Complexité spatiale :

O(n) — mémoire supplémentaire nécessaire pour stocker les sous-tableaux temporaires.

8.2 Méthode de fusion descendante

La séquence d'origine est divisée récursivement en deux jusqu'à ce que nous obtenions des sous-séquences d'un élément. À partir des sous-séquences obtenues, nous formons des paires ordonnées par la méthode de fusion, puis — des quatuors ordonnés, et ainsi de suite.

Considérons la séquence :

Nous divisons la séquence en 2 moitiés (récursivement, jusqu'à obtenir des paires).

Chaque sous-séquence est ordonnée par la méthode de fusion et nous obtenons une séquence finale.

8.3 Implémentation de l'algorithme de tri par fusion

C'est là que la récursivité entre en jeu ! C'est un très bon et rapide algorithme par rapport aux précédents. Il divise le tableau en deux, trie chaque partie séparément, puis fusionne rapidement les parties triées.

Voici à quoi ressemble son implémentation :

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Nous trouvons le milieu du tableau
        left_half = arr[:mid]  # Nous divisons le tableau en deux sous-tableaux
        right_half = arr[mid:]
        
        merge_sort(left_half)  # On trie récursivement la moitié gauche
        merge_sort(right_half)  # On trie récursivement la moitié droite
        
        i = j = k = 0
        
        # Fusion des moitiés triées
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
        
        # Vérification des éléments restants
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

# Exemple d'utilisation :
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Tableau trié :", sorted_arr)
# Sortie : Tableau trié : [3, 9, 10, 27, 38, 43, 82]

Le point clé au tout début :

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2 # Nous trouvons le milieu du tableau
        left_half = arr[:mid] # Nous divisons le tableau en deux sous-tableaux right_half = arr[mid:]
        
        merge_sort(left_half)  # On trie récursivement la moitié gauche
        merge_sort(right_half)  # On trie récursivement la moitié droite

Voici ce qui se passe ici :

1. Nous trouvons le milieu du tableau
2. Nous divisons le tableau en 2 parties
3. Nous trions chaque partie séparément

Cette approche accélère considérablement l'algorithme.