Tri par insertion

Cet algorithme de tri consiste à séparer le tableau en deux parties: la partie gauche qui est toujours triée, et la partie droite qui ne l'est pas nécessairement. Au départ la partie gauche est vide, et la partie droite prend tout le tableau. On insère une par une les valeurs de la partie gauche dans la partie droite de façon à maintenir l'ordre dans la partie gauche.

Pseudo-code

Entrée: T un tableau de n éléments
Sortie: T a été modifié et est trié dans l'ordre croissant

Principe

L'indice i de la boucle extérieure pointe vers la case que l'on va insérer dans la partie triée du tableau. L'indice j de la boucle intérieure pointe vers la valeur courante que l'on est en train d'insérer au fil de la procédure d'insertion. On décale cette valeur vers la gauche tant qu'elle n'est pas à la bonne place, c'est à dire tant que T[j] < T[j-1].

Terminaison et complexité

Cet algorithme contient deux boucles imbriquées, chacune faisant au plus n passages, et le corps de la boucle intérieure s'exécute en temps constant. La complexité de l'algorithme est donc en O(n2) .

Correction

La boucle intérieure (lignes 2 à 5) a pour effet d'insérer T[i] dans la partie T[0..i]. Sa spécification peut s'exprimer: "Si T[0..i[" est trié en entrée de la boucle intérieure, alors T[0..i] est trié en sortie de la boucle intérieure". Pour montrer cela, on peut voir qu'au fil de l'insertion, toutes les cases déjà dépassées par j sont plus grandes que la valeur à insérer. On peut donc montrer l'invariance de la propriété suivante: "T[j..i[ est trié, et T[0..i[ est trié en ignorant la case j". Graphiquement, à chaque passage sur la condition de la boucle while, la partie verte est triée, en ignorant la case rouge, et la partie de droite est triée même en incluant la case rouge.
La boucle extérieure a pour invariant: "T[0..i[ est trié". Graphiquement, la partie en vert est triée à chaque passage ligne 1. Contrairement au tri par sélection, les éléments de cette partie ne sont pas forcément au bon endroit du tableau dans l'absolu, mais leurs positions relatives sont correctes.
A la fin de l'exécution, i vaut n, et l'invariant de la boucle extérieure donne bien que T[0..n[, c'est à dire T tout entier, est trié.