Tri par insertion
NSI Terminale
Définition
Le tri par insertion est un algorithme de tri qui construit le tableau trié élément par élément : à chaque étape, il prend l'élément courant et l'insère à sa bonne place parmi les éléments déjà triés à sa gauche. C'est un tri en place (sans tableau auxiliaire) et stable. Sa complexité temporelle est en $O(n^2)$ dans le pire cas, mais en $O(n)$ si le tableau est déjà trié. Il est efficace sur les petits tableaux ou les tableaux presque triés.
Formule
$$C_{\text{pire}}(n) = O(n^2) \qquad C_{\text{meilleur}}(n) = O(n)$$
Exemple corrigé
Énoncé
Trier le tableau `[5, 2, 4, 1]` par insertion croissante, en détaillant chaque étape.
Solution
On parcourt le tableau à partir du 2ᵉ élément ; chaque élément est inséré dans la partie gauche déjà triée.
Déroulé (élément courant en gras) :
- Départ : `[5, 2, 4, 1]` → on insère 2 avant 5 → `[2, 5, 4, 1]`
- `[2, 5, 4, 1]` → on insère 4 entre 2 et 5 → `[2, 4, 5, 1]`
- `[2, 4, 5, 1]` → on insère 1 en tête → `[1, 2, 4, 5]`
```python
def tri_insertion(t):
for i in range(1, len(t)):
cle = t[i]
j = i - 1
while j >= 0 and t[j] > cle:
t[j + 1] = t[j] # décalage vers la droite
j = j - 1
t[j + 1] = cle # insertion de la clé
return t
print(tri_insertion([5, 2, 4, 1])) # [1, 2, 4, 5]
```
$$\boxed{[5, 2, 4, 1] \longrightarrow [1, 2, 4, 5]}$$
Erreurs classiques
- Démarrer la boucle à l'indice 0 au lieu de 1 : le premier élément est déjà considéré comme trié.
- Oublier de décaler les éléments avant d'insérer la clé, ou utiliser `>=` au lieu de `>` dans la comparaison, ce qui casse la stabilité du tri.
Pour aller plus loin : le chapitre « Algorithmique avancée » (cours et exercices corrigés).