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
Soit la fonction récursive suivante : ```python def mystere(n): if n == 0: return 1 else: return n * mystere(n - 1) ``` 1. Identifiez le cas de base et le cas récursif. 2. Tracez l'exécution de mystere(4) en dessinant la pile d'appels. 3. Que calcule cette fonction ?
Corrige cet exercice avec le tuteur →Exercice 2
On souhaite implémenter la **recherche dichotomique** sur un tableau trié. 1. Écrivez une fonction récursive `recherche_dichotomique(tab, cible, gauche, droite)` qui retourne l'indice de `cible` dans `tab`, ou -1 si absent. 2. Analysez la complexité temporelle en fonction de la taille n du tableau. 3. Testez avec `tab = [1, 3, 5, 7, 9, 11]` et `cible = 7`.
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique avancée (NSI Terminale).