Tri fusion en Python
Le tri fusion divise récursivement puis fusionne les sous-listes triées.
Qu’est-ce que Tri fusion en Python ?
Le tri fusion divise récursivement puis fusionne les sous-listes triées.
Trier avec l’approche diviser pour régner.
Quand l’utiliser ?
- Comprendre les algorithmes et structures de données.
- Observer chaque étape et traiter les cas limites.
- Comparer temps d’exécution et mémoire.
Visualisation de Tri fusion en Python
O(n log n)Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.
Code d’exemple
main.py
def merge_sort(values):
if len(values) <= 1:
return values
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
result = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
return result + left[left_index:] + right[right_index:]
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))Résultat attendu
[3, 9, 10, 27, 38, 43, 82]Fonctionnement
Il garantit O(n log n) en temps et utilise O(n) de mémoire supplémentaire.
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices pratiques
Modifiez les entrées et testez les cas limites avant d’utiliser des données plus volumineuses.
- Testez une entrée vide, un élément et des doublons.
- Affichez l’état après chaque étape.
- Comparez les performances avec une autre solution.