Tri par insertion en 1ère
Tri par insertion, c'est une notion de mathématiques du chapitre « Algorithmique et programmation Python », au programme de 1ère. Voici le cours, un exemple et de quoi t'entraîner.
Tri par insertion : le cours
Le tri par insertion prend chaque élément et l'insère à la bonne place dans la partie déjà triée. C'est comme ranger des cartes dans ta main : tu ajoutes chaque nouvelle carte au bon endroit.
Exemple
Tu reçois des cartes une par une au poker : tu les ranges dans ta main en mettant chaque nouvelle carte à sa place parmi celles que tu as déjà.
À retenir
Le tri par insertion a une complexité en $O(n^2)$ en moyenne, mais il est rapide si la liste est presque triée.
S'entraîner sur tri par insertion
Fais l'exercice, puis demande au tuteur de te corriger pas à pas.
Exercice 1
Écris une fonction recherche_dichotomie(liste, cible) qui cherche cible dans une liste triée et retourne son index (ou -1 si absent). Teste avec assert recherche_dichotomie([1, 3, 5, 7, 9], 5) == 2.
Corrige cet exercice avec le tuteur →Exercice 2
Écris une fonction tri_insertion(liste) qui trie une liste en place par insertion. Teste avec assert tri_insertion([3, 1, 4, 1, 5]) == [1, 1, 3, 4, 5].
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique et programmation Python (Mathématiques 1ère).