Tutoriel sur l'algorithme de tri par fusion Python

Découvrez comment implémenter le tri par fusion en Python. Un exemple interactif, étape par étape, de la stratégie de tri Diviser pour régner.

Essayez dans l'éditeur

Aperçu

Merge Sort est un algorithme de tri très efficace qui utilise une stratégie diviser pour régner. Il décompose une liste non triée en sous-listes plus petites, trie ces sous-listes, puis les fusionne.

L'algorithme divise récursivement le tableau en deux jusqu'à ce qu'il atteigne des sous-tableaux à un seul élément. Ensuite, il fusionne les sous-tableaux triés en comparant les éléments de chaque côté et en les plaçant dans l'ordre trié. Cela garantit une complexité temporelle optimale.

Que le tableau initial soit trié, inversé ou complètement aléatoire, le tri par fusion s'exécute en un temps O(n log n). Cependant, cela nécessite O(n) d'espace supplémentaire pour contenir les sous-listes pendant la phase de fusion.

Sortie de code et d'exécution

Une implémentation récursive standard de l'algorithme Merge Sort en Python.

merge_sort.py

Essayez dans l'éditeur

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
        
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Test dataset
data = [38, 27, 43, 3, 9, 82, 10]
print("Original List:", data)
sorted_data = merge_sort(data)
print("Sorted List:  ", sorted_data)

Sortie terminale

Original List: [38, 27, 43, 3, 9, 82, 10]
Sorted List:   [3, 9, 10, 27, 38, 43, 82]

Mise en œuvre étape par étape

Tri des listes chaînées où la structure des nœuds facilite la fusion facile sans copie
Routines de tri externes pour les fichiers qui ne rentrent pas entièrement dans la RAM système
Applications de tri stables où les clés correspondantes doivent conserver leur ordre d'origine

Foire aux questions

Merge Sort est-il un algorithme de tri stable ?

Oui, le tri par fusion est stable. Lors de la comparaison d'éléments identiques, l'élément du sous-tableau de gauche (original en premier) est placé en premier, en préservant ses positions relatives d'origine.

Pourquoi Python utilise-t-il Timsort au lieu du tri par fusion pur ?

Le « sorted() » intégré de Python utilise Timsort, qui est un algorithme hybride combinant le tri par fusion et le tri par insertion. Il optimise les modèles de données du monde réel en identifiant les sous-segments déjà triés, ce qui le rend plus rapide que le tri par fusion pur.

Sujets connexes

Guide de l'algorithme de tri rapide Python

Explorez l'algorithme de tri rapide en Python. Apprenez la sélection pivot, le partitionnement et la récursivité dans cet exemple de codage interactif.

Algorithmes de tri Python

Explorez les algorithmes de tri Python. Visualisez le tri par bulles et le tri par fusion de manière native dans un contexte IDE de navigateur.

Algorithme de recherche binaire Python

Recherchez des listes triées en temps logarithmique O (log n). Exécutez et comprenez la recherche binaire en Python, y compris la logique étape par étape, les cas extrêmes et les optimisations.