Tri Fusion (Merge Sort)
Diviser pour régner — O(n log n)
Enonce
Implémenter le tri fusion récursif. La fonction tri_fusion retourne une nouvelle liste triée.
⚠ Bonus : Écrire une fonction fusionner(G, D) séparée.
Signature attendue
def tri_fusion(T: list) -> list:Exemples
tri_fusion([38, 27, 43, 3, 9, 82, 10])→[3, 9, 10, 27, 38, 43, 82]tri_fusion([5, 1, 4, 2, 8])→[1, 2, 4, 5, 8]tri_fusion([1])→[1]
📖 Rappel de cours
Le tri fusion est un algorithme diviser pour régner. On divise le tableau en deux moitiés, on trie récursivement, puis on fusionne les deux moitiés triées.
📚 Analogie — Trier des copies d'examen :
Vous avez une grosse pile de copies à trier par note. Vous la coupez en deux, vous donnez chaque moitié à un collègue, chacun trie sa moitié. Ensuite vous fusionnez les deux piles triées en comparant les copies du dessus une par une. C'est récursif : chaque collègue peut lui-même couper sa pile en deux !
Récurrence :
$T(n) = 2\,T\!\left(\frac{n}{2}\right) + O(n) \Longrightarrow T(n) = O(n\log n)$
La fusion de deux listes triées de taille $n/2$ se fait en $O(n)$.
Avantage : complexité garantie $O(n\log n)$. Inconvénient : $O(n)$ en mémoire.
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Tri à Bulle (Bubble Sort)
- Tri par Insertion
- Tri par Sélection
- Tri Rapide (Quicksort)
- Exponentiation Rapide
- Recherche dans une Liste Chaînée
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.