Tri fusion vs Tri rapide en Python : Analyse comparative et implémentation

Les algorithmes de tri sont fondamentaux en informatique, et deux des plus célèbres sont le tri fusion (merge sort) et le tri rapide (quicksort). Dans cet article, nous allons plonger dans une analyse comparative approfondie de ces deux algorithmes, tout en explorant leur implémentation en Python.

Comprendre les algorithmes

Tri fusion (Merge Sort)

Le tri fusion est un algorithme de type  » diviser pour régner  » qui fonctionne ainsi :

1. Diviser la liste en deux moitiés
2. Trier récursivement chaque moitié
3. Fusionner les deux moitiés triées

Tri rapide (Quicksort)

Le tri rapide, également de type  » diviser pour régner « , fonctionne différemment :

1. Choisir un élément pivot
2. Partitionner la liste autour du pivot
3. Trier récursivement les sous-listes à gauche et à droite du pivot

Implémentation en Python

Implémentation du tri fusion

def tri_fusion(arr):
    if len(arr) <= 1:
        return arr
    
    milieu = len(arr) // 2
    gauche = tri_fusion(arr[:milieu])
    droite = tri_fusion(arr[milieu:])
    
    return fusionner(gauche, droite)

def fusionner(gauche, droite):
    resultat = []
    i, j = 0, 0
    
    while i < len(gauche) and j < len(droite):
        if gauche[i] < droite[j]:
            resultat.append(gauche[i])
            i += 1
        else:
            resultat.append(droite[j])
            j += 1
    
    resultat.extend(gauche[i:])
    resultat.extend(droite[j:])
    
    return resultat

# Exemple de liste à trier
exemple_liste = [38, 27, 43, 3, 9, 82, 10]

# Tri de la liste
liste_triee = tri_fusion(exemple_liste)

# Affichage du résultat
print("Liste originale :", exemple_liste)
print("Liste triée :", liste_triee)

Implémentation du tri rapide

def tri_rapide(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    gauche = [x for x in arr if x < pivot]
    milieu = [x for x in arr if x == pivot]
    droite = [x for x in arr if x > pivot]
    
    return tri_rapide(gauche) + milieu + tri_rapide(droite)


# Exemple de liste à trier
exemple_liste = [38, 27, 43, 3, 9, 82, 10]

# Tri de la liste
liste_triee = tri_rapide(exemple_liste)

# Affichage du résultat
print("Liste originale :", exemple_liste)
print("Liste triée :", liste_triee)

Analyse comparative

Complexité temporelle

• Tri fusion : O(n log n) dans tous les cas
• Tri rapide : O(n log n) en moyenne, O(n^2) dans le pire cas

Complexité spatiale

• Tri fusion : O(n)
• Tri rapide : O(log n) en moyenne (en place), O(n) dans le pire cas

Stabilité

• Tri fusion : Stable
• Tri rapide : Non stable (dans l’implémentation classique)

Performance sur différents types de données

1. Listes presque triées :
   • Tri fusion : Performant
   • Tri rapide : Peut être lent (dépend du choix du pivot)
2. Listes avec beaucoup de doublons :
   • Tri fusion : Performant
   • Tri rapide : Peut être inefficace (dépend de l’implémentation)

Cas d’utilisation

• Tri fusion :
  • Excellent pour les grands ensembles de données
  • Idéal lorsqu’une stabilité est requise
  • Efficace pour les structures de données externes (tri de fichiers)
• Tri rapide :
  • Souvent plus rapide en pratique pour les petites à moyennes listes
  • Bon choix lorsque l’espace mémoire est limité (version en place)
  • Performant pour les tableaux stockés en mémoire

Optimisations possibles

1. Tri fusion :
   • Utiliser l’insertion sort pour les petites sous-listes
   • Optimiser la fusion pour réduire les copies
2. Tri rapide :
   • Choisir intelligemment le pivot (médian de trois)
   • Utiliser l’insertion sort pour les petites sous-listes
   • Implémenter une version non récursive pour éviter le débordement de pile

Conclusion

Le choix entre le tri fusion et le tri rapide dépend de votre cas d’utilisation spécifique. Le tri fusion est plus prévisible et stable, tandis que le tri rapide peut être plus rapide dans de nombreux cas pratiques.

Lire Aussi :
Comment implémenter une recherche binaire en Python : Un guide étape par étape
Projet Python : Outil OCR Open-Source pour l’Analyse de Documents