Le tri fusion
Diviser, trier chaque moitié, fusionner : la fusion de deux suites triées, l'ordre des appels récursifs, le coût en n log n, la mémoire auxiliaire et la stabilité.
- 23 cartes
- 4 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
Quelques cartes du deck
Tri fusion : de quoi s'agit-il ?
Voir la réponse
Tri qui coupe la suite en deux moitiés, trie chacune récursivement, puis réunit les deux moitiés triées en une seule suite triée.
Tout le travail est dans la réunion : trier une suite d'un seul élément ne coûte rien, et fusionner deux suites triées se fait en un seul passage.
Combien de comparaisons au plus pour fusionner deux suites triées de 3 et de 5 éléments ?
- 7
- 8
- 15
- 5
Voir la réponse
7
Chaque comparaison place un élément dans le résultat, sauf que le dernier élément restant est recopié sans comparaison : au plus 3 + 5 − 1 = 7.
Le tri fusion trie la moitié …, puis la moitié …, et enfin … les deux résultats.
Voir la réponse
Le tri fusion trie la moitié gauche, puis la moitié droite, et enfin fusionne les deux résultats.
La fusion n'a lieu qu'au retour des deux appels récursifs : les petites suites sont donc fusionnées avant les grandes.
Fusion de deux suites triées : de quoi s'agit-il ?
Voir la réponse
Opération qui compare les têtes des deux suites, retire la plus petite pour la poser dans le résultat, et recommence jusqu'à épuisement d'une suite, puis recopie le reste de l'autre.
Comme chaque suite est déjà triée, le plus petit élément restant est toujours en tête de l'une des deux : un seul passage de n éléments suffit, soit O(n).