Tri par insertion

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 $c_1$), 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 $\frac{j}{2}$ fois.

Le corps de la boucle while s’exécute en un temps $c_2$ indépendant de $n$.

Le temps d’exécution total dans le cas moyen est donc :

$\sum _{j=1}^{n-1}(c_1+c_2\times \frac{j}{2})=(n-1)c_1+\frac{c_2}{2}\frac{n(n-1)}{2}=\Theta \left(n^2\right)$

Dans le cas le pire, en changeant $\frac{j}{2}$ en $j$, le coût reste quadratique. Il est par contre linéaire si la liste est déjà triée.