Diviser pour régner : tri fusion en Terminale
Diviser pour régner : tri fusion, c'est une notion de nsi du chapitre « Algorithmique avancée », au programme de Terminale. Voici le cours, un exemple et de quoi t'entraîner.
Diviser pour régner : tri fusion : le cours
Le tri fusion divise le tableau en deux moitiés, les trie récursivement, puis les fusionne. C'est un algorithme en $O(n \log n)$ très efficace et stable.
Exemple
Trier une pile de 100 examens : tu les divises en deux piles de 50, tu tries chaque pile, puis tu les mets ensemble en ordre.
À retenir
Le tri fusion est plus lent que le tri rapide en moyenne mais garantit toujours $O(n \log n)$ et préserve l'ordre des éléments égaux.
S'entraîner sur diviser pour régner : tri fusion
Fais l'exercice, puis demande au tuteur de te corriger pas à pas.
Exercice 1
Écris une fonction récursive avec mémoïsation pour calculer le nombre de façons de monter un escalier de n marches si tu peux monter 1 ou 2 marches à la fois. Quelle est la complexité sans et avec mémoïsation ?
Corrige cet exercice avec le tuteur →Exercice 2
Implémente un BFS pour trouver le chemin le plus court entre deux nœuds dans un graphe représenté par une liste d'adjacence. Pourquoi BFS et pas DFS ?
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique avancée (NSI Terminale).