← Retour aux activités

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.

CasComplexité
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é."

4 Exercices d'application

5 Défis de programmation