Le Tri par Insertion
Le tri par insertion (ou insertion sort) est l'algorithme que la plupart des gens utilisent naturellement pour trier des cartes à jouer dans leur main. On prend un élément et on l'insère à sa juste place parmi les éléments déjà triés.
1 Animation JavaScript
Cliquez sur "Démarrer" pour visualiser l'algorithme
Légende : ■ Élément à insérer | ■ Comparaison | ■ Partie triée
2 L'Algorithme
PROCÉDURE tri_insertion(tableau T)
n = longueur(T)
POUR i DE 1 À n-1
cle = T[i]
j = i - 1
TANT QUE j >= 0 ET T[j] > cle
T[j + 1] = T[j]
j = j - 1
FIN TANT QUE
T[j + 1] = cle
FIN POUR
FIN PROCÉDURE
def tri_insertion(tab):
n = len(tab)
for i in range(1, n):
cle = tab[i]
j = i - 1
while j >= 0 and tab[j] > cle:
tab[j + 1] = tab[j]
j = j - 1
tab[j + 1] = cle
return tab
3 Complexité et Propriétés
Complexité temporelle
Le tri par insertion est dit adaptatif car ses performances dépendent de l'ordre initial des éléments.
| Cas | Complexité |
|---|---|
| Pire cas (Tableau trié à l'envers) | $O(n^2)$ |
| Meilleur cas (Tableau déjà trié) | $O(n)$ |
| Complexité moyenne | $O(n^2)$ |
Terminaison
La boucle externe (for) est finie. La boucle interne (while) possède un variant de boucle $j+1$ (car $j$ décroît mais est minoré par -1) qui assure qu'elle s'arrêtera.
Correction
L'invariant de boucle est : "Au début de chaque itération $i$, le sous-tableau composé des éléments de $0$ à $i-1$ est trié."