Le tri par insertion

C'est le tri du joueur de cartes. On fait comme si les éléments à trier étaient donnés un par un, le premier élément constituant, à lui tout seul, une liste triée de longueur 1. On range ensuite le second élément pour constituer une liste triée de longueur 2, puis on range le troisième élément pour avoir une liste triée de longueur 3 et ainsi de suite...

Le principe du tri par insertion est donc d'insérer à la n_ième itération le n_ième élément à la bonne place.

L'animation ci-après illustre le fonctionnement de ce tri :

Démonstration du tri par insertion

Pseudo-code

PROCEDURE tri_Insertion ( Tableau a[1:n])
POUR i VARIANT DE 2 A n FAIRE
INSERER a[i] à sa place dans le Tableau a[1:i-1];
FIN PROCEDURE;

let tri_insertion tableau =
for i = 1 to 19 do
let en_cours = tableau.(i) and j = ref (i - 1) in
(* Décalage des éléments du tableau *)
while (!j>=0) && (tableau.(!j)>en_cours) do
tableau.(!j + 1) <- tableau.(!j);
j := !j - 1;
done;
(* on insère l'élément à sa place *)
tableau.(!j + 1) <- en_cours;
done;
tableau;;

type tab = array[1..20] of integer;
procedure tri_insertion(var tableau : tab);
var i, j, en_cours : integer;
begin
for i:=2 to 20 do
begin
en_cours := tableau[i]; j := i - 1;
{décalage des éléments du tableau }
while (j > 0) and (tableau[j] > en_cours) do
begin
tableau[j + 1] := tableau[j];
j := j - 1;
end;
{on insère l'élément à sa place }
tableau[j + 1] := en_cours;
end;
end

Correction de l'algorithme de tri par insertion

Dans notre algorithme de tri par insertion, l'invariant de boucle est "Le tableau a[1:i] est trié" :

INITIALISATION : La valeur avant de rentrer dans la boucle est i=1, donc le tableau a[1:1] contient un seul élément. Un tableau contenant un seul élément est forcément trié (trivial), notre invariant "le tableau a[1:i] est trié" est donc vrai.

CONSERVATION : si l'invariant de boucle est vrai avant une itération de la boucle : "Le tableau a[1:i-1] est trié", alors il le reste à la fin de l'itération : "Le tableau a[1:i] est trié".
Si on insère a[i] à sa place dans le tableau a[1:i-1], alors le tableau a[1:i] sera évidemment trié.

TERMINAISON : La dernière valeur prise de i dans la boucle est i=n, donc le tableau a[1:n] sera trié.

Cette démonstration nous permet d'affirmer que l'algorithme de tri par insertion est correct.

Complexité de l'algorithme de tri par insertion

Pour évaluer la complexité d'un algorithme il faut envisager le pire des cas, ici lorsque la liste est classée dans l'ordre décroissant.

On suppose que notre liste à n éléments, on va essayer de compter le nombres d'opérations nécessaires pour obtenir la liste triée.

Donc la complexité est de l'ordre de n², on dira que le coût est quadratique.

Interprétation

Un exercice

On utilise un algorithme de tri de coût quadratique. Il met 1,6 secondes pour trier un liste de 100 000 nombres.
Quel sera le temps approximativement pour trier 50 000 nombres ?

Solution
On calcule le rapport des nombres d'éléments de chaque liste : pour passer de 100 000 à 50 000 on multiplie par 0,5.
Donc le temps sera multiplié par 0,5² = 0,25. Soit 1,6 × 0,25 = 0,4 seconde.