Tri par Insertion
Invariant de boucle et preuve
Enonce
Implémenter le tri par insertion en place (retourne None).
Signature attendue
def tri_insertion(T: list) -> None:Exemple
T = [5, 2, 8, 1, 9, 3] ; tri_insertion(T) ; T→[1, 2, 3, 5, 8, 9]
📖 Rappel de cours
🃏 Analogie — Le jeu de cartes :
Imaginez que vous triez une main de cartes. Vous prenez les cartes une par une de la gauche vers la droite. Pour chaque nouvelle carte, vous la glissez vers la gauche jusqu'à trouver sa bonne place parmi les cartes déjà triées dans votre main. C'est exactement ce que fait le tri par insertion !
Invariant :
Après l'itération $i$, $T[0..i]$ est trié.
Pire cas : $O(n^2)$ | Meilleur cas : $O(n)$
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Recherche Dichotomique
- Suite de Fibonacci
- Tri à Bulle (Bubble Sort)
- Tri par Sélection
- Tri Fusion (Merge Sort)
- Tri Rapide (Quicksort)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.