Tutoriel sur le tri fusion en Python

Le tri des données est l’une des opérations les plus courantes effectuées par les praticiens des données dans leur travail quotidien. Bien des fois, nous devons afficher les données dans un certain ordre pour en extraire des informations significatives. Heureusement, de nos jours, nous n’avons plus à effectuer cette tâche manuellement. Les ordinateurs peuvent faire la magie pour nous avec des performances imbattables.

Il existe plusieurs stratégies pour trier des données. Dans ce tutoriel, nous analyserons l’une des techniques de tri les plus efficaces. L’algorithme « tri fusion » utilise une stratégie de diviser pour régner pour trier un tableau non trié en le divisant d’abord en plus petits tableaux, qui sont ensuite fusionnés dans le bon ordre.

Dans les prochaines sections, nous discuterons de tous les détails de l’algorithme de tri fusion, de son apparence en Python et de quelques conseils pratiques pour une mise en œuvre fluide.

Qu’est-ce que le tri fusion ?

Il existe de nombreux algorithmes de tri, mais il est difficile d’en trouver un qui fonctionne mieux que le tri fusion. Sans surprise, cet algorithme est utilisé dans toutes sortes d’applications du monde réel, comme le tri de grandes bases de données ou l’organisation de fichiers sur un ordinateur ordinaire.

L’algorithme est basé sur le paradigme diviser pour régner, qui peut être décomposé en trois parties :

• Diviser : ce processus divise le problème en sous-problèmes plus petits.
• Régner : les sous-problèmes sont résolus de manière récursive.
• Combinaison : les solutions des sous-problèmes sont combinées afin d’obtenir la solution finale.

Stratégie de diviser pour régner

Voyons comment fonctionne le tri par fusion. Supposons que nous voulions ordonner les nombres suivants en appliquant l’algorithme de tri par fusion. L’algorithme divise les données de manière récursive en deux parties et continue de diviser jusqu’à ce que chaque liste ait un élément. Ensuite, nous les combinons en les triant dans une autre liste.

Problème de tri par fusion. Source : DataCamp

Complexité en temps et en espace du tri par fusion

Il est impossible de savoir à l’avance quel est l’algorithme de tri qui fonctionne le mieux pour un certain problème. Plusieurs variables doivent être prises en compte au-delà de l’algorithme, y compris le langage de programmation utilisé pour écrire le code, le matériel sur lequel ils sont exécutés, et les particularités des données à trier.

Bien que nous ne puissions pas prédire le temps d’exécution exact d’un algorithme de tri, nous pouvons tout de même comparer les performances de divers algorithmes de tri en analysant la complexité en temps et en espace.

Complexité en temps du tri par fusion

Comme nous l’avons expliqué dans un guide séparé sur la notation Big O et la complexité temporelle, l’objectif de l’analyse de la complexité temporelle n’est pas de prédire le temps d’exécution exact d’un algorithme, mais plutôt d’évaluer l’efficacité d’un algorithme en analysant comment son temps d’exécution change à mesure que la quantité de données d’entrée augmente.

L’analyse de la complexité temporelle s’écrit en notation Big O, une notation mathématique qui décrit le rythme auquel une fonction croît ou décline. Le tri par fusion a une complexité temporelle log-linéaire ou linarithmique, notée O(N log(N)), où N est le nombre d’éléments dans la liste. La lettre ‘O’ représente ‘l’ordre’ de croissance.

Dans l’analyse de la complexité temporelle, la complexité linarithmique se comporte à peu près de manière similaire à la complexité linéaire, ce qui signifie que son exécution sera directement proportionnelle à la quantité de données. Ainsi, si la quantité de données est doublée, le temps nécessaire à l’algorithme pour traiter les données devrait également doubler, c’est-à-dire que le nombre de divisions et de fusions doublera.

Parce que la complexité temporelle du tri par fusion se comporte de manière linéaire, sa complexité reste la même pour les meilleurs, moyens et pires cas. Cela signifie que, indépendamment de l’ordre d’entrée, l’algorithme prendra toujours le même nombre d’étapes pour se terminer.

Complexité spatiale du tri par fusion

Enfin, en plus du temps nécessaire pour terminer la tâche, un autre aspect important lors de l’analyse de la complexité des algorithmes est d’estimer combien de mémoire l’algorithme nécessitera pour se compléter à mesure que le problème devient plus grand.

Cela est couvert par les concepts de complexité spatiale et d’espace auxiliaire. Ce dernier fait référence à l’espace supplémentaire ou temporaire utilisé par un algorithme, tandis que le premier fait référence à l’espace total occupé par l’algorithme par rapport à la taille de l’entrée. En d’autres termes, la complexité spatiale inclut à la fois l’espace auxiliaire et l’espace utilisé par l’entrée.

Le tri fusion a une complexité spatiale de O(N). Cela est dû au fait qu’il utilise un tableau auxiliaire de taille N pour fusionner les moitiés triées du tableau d’entrée. Le tableau auxiliaire est utilisé pour stocker le résultat fusionné, et le tableau d’entrée est écrasé avec le résultat trié.

Implémentation du tri fusion en Python

Implémentons l’algorithme de tri fusion en Python. Il existe plusieurs façons de coder l’algorithme ; cependant, nous nous en tiendrons à celui basé sur la récursion, qui est sans doute le plus facile à comprendre et nécessite moins de lignes de code que d’autres alternatives basées sur l’itération.

Compréhension de la récursion dans le tri fusion

Si vous êtes nouveau sur le sujet, en programmation, la récursion se produit lorsque une fonction s’appelle elle-même. Vous pouvez consulter notre Tutoriel sur la Compréhension des Fonctions Récursives en Python pour tout apprendre sur ces fonctions puissantes.

Pour implémenter le tri fusion, nous commençons par définir le cas de base : si la liste ne contient qu’un seul élément, elle est déjà triée, donc nous retournons immédiatement. Sinon, nous divisons la liste en deux moitiés, left_half et right_half, et appelons merge_sort() récursivement sur chacune d’elles. Ce processus se poursuit jusqu’à ce que toutes les sous-listes contiennent un seul élément.

Une fois que nous avons ces sous-listes triées, nous commençons le processus de fusion. Pour ce faire, nous initialisons trois variables d’index : i pour suivre la position dans left_half, j pour right_half, et k pour la liste fusionnée finale. Ensuite, nous comparons les éléments des deux moitiés. Si l’élément actuel dans left_half est plus petit, nous le plaçons dans my_list[k] et déplaçons i vers l’avant. Sinon, nous prenons l’élément de right_half, le plaçons dans my_list[k], et incrémentons j. Après chaque comparaison, nous déplaçons k vers la position suivante dans la liste finale.

Ce processus se poursuit jusqu’à ce que nous ayons comparé tous les éléments dans l’une des moitiés. S’il reste des éléments dans left_half ou right_half, nous les ajoutons directement à la liste finale, garantissant qu’aucune donnée n’est laissée derrière. Comme le tri fusion fonctionne de manière récursive, ce processus de fusion est exécuté à chaque niveau de récursion jusqu’à ce que la liste entière soit triée.

Implémentation en Python

Ci-dessous, vous pouvez trouver le code utilisant la liste non triée du diagramme précédent comme exemple :

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]

Tri par fusion vs Autres algorithmes de tri

Le tri par fusion est un algorithme de tri assez rapide, particulièrement bien adapté aux grandes bases de données, et il est souvent utilisé comme référence pour d’autres algorithmes. Cependant, en ce qui concerne les listes plus courtes, ses performances tendent à être inférieures à celles d’autres algorithmes de tri.

Dans le tableau suivant, vous pouvez trouver une comparaison du tri par fusion avec d’autres algorithmes de tri populaires.

Applications pratiques du tri par fusion

Le tri par fusion a une performance élevée lors du tri de grandes listes, mais son efficacité diminue lorsqu’il s’agit de listes plus petites. De même, il a tendance à être moins efficace dans des scénarios où il y a déjà un certain degré d’ordre dans les listes d’entrée, car le tri par fusion effectuera les mêmes étapes quelle que soit l’ordre de la liste.

Un excellent cas d’utilisation où le tri par fusion est particulièrement utile est celui des listes chaînées. Une liste chaînée est une structure de données qui comprend une connexion de nœuds liés entre eux de manière linéaire. Chaque nœud contient les données et le lien pour se connecter au nœud suivant.

Le tri par fusion est préféré pour les listes chaînées car il nécessite uniquement un accès séquentiel aux données, ce qui correspond bien à la nature des listes chaînées. De plus, le tri par fusion est un algorithme de tri stable (c’est-à-dire qu’il préserve l’ordre relatif des éléments égaux dans la sortie triée), ce qui est une considération très importante pour maintenir l’ordre des listes chaînées.

Erreurs courantes et dépannage

L’algorithme de tri par fusion est assez simple, et la marge d’amélioration dans le code est limitée. Cependant, vous pouvez augmenter la complexité de votre stratégie de tri en tenant compte de la taille des données d’entrée.

Nous avons déjà établi que le tri par fusion fonctionne mieux avec de plus grands ensembles de données. Pour des ensembles de données plus petits, d’autres algorithmes de tri avec une complexité temporelle O(N^2), comme le tri par insertion, peuvent mieux fonctionner. Dans ce cas, vous devrez simplement créer un seuil de taille en dessous duquel vous opteriez pour l’algorithme de tri par insertion au lieu du tri par fusion.

Sinon, une bonne idée à explorer serait la parallélisation. Les étapes du tri fusion peuvent être facilement parallélisées avec la puissance de calcul adéquate, réduisant ainsi le temps de traitement. Consultez notre guide Processeur vs GPU pour en savoir plus sur le calcul parallèle.

Conclusion

Le tri fusion est l’un des algorithmes de tri les plus efficaces et populaires, mais il y a encore beaucoup à apprendre dans l’univers merveilleux et en constante expansion des algorithmes. Si vous êtes intéressé par les aspects techniques des algorithmes, leur fonctionnement, leur complexité, leurs vertus et leurs inconvénients, ces ressources de DataCamp peuvent vous aider à poursuivre votre apprentissage :

• Cours d’Introduction aux Structures de Données et Algorithmes
• Parcours de Compétences en Programmation Python
• Parcours de Fondamentaux des Données en Python
• Cours de Python Intermédiaire
• Parcours de Carrière d’Analyste de Données en Python
• Notation Big O et Complexité Temporelle