Le tri par insertion est un tri facile à implémenter. Son coût dans le cas le pire est quadratique. Toutefois, il offre de bons résultats sur des listes de peu d’éléments ou partiellement triées.
I. Présentation de l’algorithme
On parcourt tous les éléments, chacun est inséré à sa place dans les éléments déjà triés qui le précèdent.
Propriétés du tri par insertion :
• tri en place, il n’est pas nécessaire de faire une copie de la liste ;
• tri stable, deux éléments égaux resteront dans le même ordre ;
• tri en ligne, les éléments de la liste pourraient être fournis au fur et à mesure.
Exemple en Python d’une fonction de tri par insertion :
II. Preuve de correction
Montrons qu’à la fin d’un tour de la boucle for, les valeurs de la liste lst sont triées jusqu’à la case j incluse.
Au début, j vaut 1 et la liste, réduite à la case d’indice 0, est bien triée.
Supposons qu’à la fin du tour j - 1 les valeurs de la liste soient triées jusqu’à la case j - 1 incluse. On montre que lors du tour j, la case cle = lst[j] sera insérée correctement et que la liste sera ainsi triée jusqu’à la case j incluse. On envisage deux cas.
Cas 1 : lst[j] >= lst[0].
• On est dans cette situation avant la ligne 3 :
• Puis après la ligne 4 :
• On entre dans la boucle while. À la fin de la boucle, avant la ligne 8, la situation est :
• Puis après la ligne 8, à la fin du tour de la boucle for :
La liste est donc triée jusqu’à la case j incluse.
Cas 2 : lst[j] < lst[0]. On vérifie sans mal que la boucle while quitte pour i = -1 et que la clé est bien insérée dans la case 0.
En conséquence, lorsque la boucle for termine son dernier tour, j désigne la dernière case et on a montré que la liste était triée jusqu’à cette case. La liste est donc entièrement triée.
III. Complexité de l’algorithme
Supposons que la taille de la liste est n.
La boucle for tourne toujours exactement n−1 fois. Les lignes 3, 4 et 8 s’exécutent en un temps constant (notons-le c1), indépendant de n.
La boucle while tourne j fois dans le pire cas (liste triée par ordre décroissant), ou pas du tout si la liste est déjà triée. Dans le cas moyen, elle tournera j2 fois.
Le corps de la boucle while s’exécute en un temps c2 indépendant de n.
Le temps d’exécution total dans le cas moyen est donc :
∑j=1n−1 (c1+c2×j2)=(n−1) c1+c22n(n−1)2=Θ(n2)
Dans le cas le pire, en changeant j2 en j, le coût reste quadratique. Il est par contre linéaire si la liste est déjà triée.