Tri par insertion

Merci !

Fiches
Classe(s) : 1re Générale | Thème(s) : Algorithmes fondamentaux


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 :

PB_Bac_05230_numerique1_TT_p213-244_C07_Groupe_Schema_5

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 :

05230_chap07_05

• Puis après la ligne 4 :

05230_chap07_06

• On entre dans la boucle while. À la fin de la boucle, avant la ligne 8, la situation est :

05230_chap07_07

• Puis après la ligne 8, à la fin du tour de la boucle for :

05230_chap07_08

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 n1 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=1n1(c1+c2×j2)=(n1) c1+c22n(n1)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.