Tri par Insertion

Admin Messages : 74 Date d'inscription : 02/03/2011

Tri par Insertion

Principe

L'algorithme principal du tri par insertion est un algorithme qui insère un élément dans une liste d'éléments déjà triés (par exemple, par ordre croissant).

Imaginez un joueur de cartes qui dispose de cartes numérotées. Il a des cartes triées de la plus petite à la plus grande dans sa main gauche, et une carte dans la main droite. Où placer cette carte dans la main gauche de façon à ce qu'elle reste triée ? Il faut la placer après les cartes plus petites, et avant les cartes plus grandes.

Par exemple, si la main gauche est (1-3-6-huit), et que j'ai la carte 5 dans la main droite, il faut la placer après (1-3) et avant (6-huit). Si l'on fait ça, on se retrouve avec la main gauche (1-3-5-6-huit), qui est encore triée.

Pour trier entièrement un ensemble de cartes dans le désordre, il suffit alors de placer toutes ses cartes dans la main droite (la main gauche est donc vide), et d'insérer les cartes une à une dans la main gauche, en suivant la procédure ci-dessus.

Au départ, la main gauche est vide, donc elle bien triée.
À chaque fois que l'on insère une carte depuis la main droite vers la main gauche, la main gauche reste triée, et la main droite (l'ensemble des cartes non triées) perd une carte. Ainsi, si la main droite comprenait au départ N cartes, en N insertions, on se retrouve avec O carte dans la main droite, et N cartes, triées, dans la main gauche : on a bien trié notre ensemble de cartes.

Commençons tout d’abord par l’opération d’insertion d’une carte de la main droite vers la main gauche. On veut placer la carte après toutes les cartes plus petites, et avant toutes les cartes plus grandes.

En reprenant notre exemple de tout à l'heure, pour insérer l'élément 5 dans la main (1-3-6-huit), voici ce qu'on veut faire :

[Vous devez être inscrit et connecté pour voir cette image]

Pour faire cela avec un tableau, on a du décaler certaines cartes : 6 était en position 2 avant l'insertion, elle est en position 3 après. De même, la carte (huit) a été décalée. Plus généralement, il faut décaler d’une case vers la droite toutes les cartes plus grandes que la carte à insérer.

Pour faire cela, une bonne méthode est de commencer par la droite : on décale la carte la plus à droite (huit), puis celle juste à gauche (6), jusqu'au moment où on tombe sur une carte plus petite que celle qu'on veut insérer, qu'il ne faut pas décaler. Une fois qu'on a fait ces décalages, on peut insérer la carte, à la position à laquelle on s'est arrêté de décaler.

[Vous devez être inscrit et connecté pour voir cette image]

Il y a une remarque importante à faire : taille_gauche est la taille de la main gauche, mais ce n’est pas la taille du tableau tab : comme on rajoute un élément, on a besoin que le tableau tab ait au moins une case de plus. Sur le dessin, ça correspond à la présence d'une case verte supplémentaire, vide, au début de l'insertion.
On suppose donc que la taille réelle de tab est toujours strictement supérieure à taille_gauche, et c’est pour cela qu’on s’autorise à écrire dans tab[taille_gauche] (au premier tour de boucle, quand j vaut taille_gauche). Quand on utilisera la fonction inserer, on vérifiera que la taille du tableau convient.

Je parcours le tableau avec l’indice i.

L’idée, c’est que je considère que toutes les cartes avant i sont triées, et que toutes les cartes après i ne sont pas triées, tab[i] compris. i est donc la limite entre la main gauche et la main droite.
Autrement dit, j'ai bien mes deux mains (heureusement !), mais ce ne sont pas deux mains séparées, elles sont ensembles dans un seul tableau : la main gauche est le début du tableau, qui est déjà trié, et la main droite le reste du tableau.

Jusqu'à présent, dans l'implémentation, je n'ai pas parlé de la main droite : on insérait seulement un élément. Cet élément est la première carte de la main droite. Par exemple, l'insertion que je vous ai montrée au départ faisait en fait partie du tri du tableau suivant, quand i vaut 4 :

[Vous devez être inscrit et connecté pour voir cette image]

Comme i est la limite entre la main droite et la main gauche, la carte d’indice i appartient avant l’insertion à la main droite, et après à la main gauche. Au début de la boucle, [0...i-1] est la main gauche, puis on insère tab[i] avec la fonction vue au-dessus, donc la main gauche devient [0..i], et reste triée.

Illustration :

[Vous devez être inscrit et connecté pour voir cette image]

En faisant varier i de 1 à taille-1 (i < taille est la condition d’arrêt), on insère donc peu à peu toutes les cartes dans la main gauche.
On remarque que la boucle commence à 1, et non à 0. La première carte, comme elle est toute seule, est déjà une liste triée, donc on peut l’inclure d’office dans la main gauche.

Vous remarquerez que la taille donnée à la fonction inserer est i. Ainsi, comme la plus grande valeur de i possible est taille-1, la plus grande taille donnée à insérer est taille-1 aussi. J’avais dit qu’on ferait attention à ce que la taille donnée pour la main gauche soit toujours inférieure à la véritable taille du tableau, et vous pouvez maintenant le vérifier.

Animation du Tri par insertion

[Vous devez être inscrit et connecté pour voir ce lien]

Téléchargement de l'animation

Taille: 16.05 KB
[Vous devez être inscrit et connecté pour voir ce lien]

Code en algorithmique (mode itérative):

Code:: procédure tri_insertion (n:entier,var T:tab)

pour c de 2 à n faire
si t[c-1]>t[c] alors
Tmp <-- t[c]
Proc decaler (t,c-1,p)
t[p+1]<--Tmp
fin si
fin pour
fin tri_insertion
procedure decaler (vat t:tab,deb:entier,var fin:entier)

tanque (fin>=1)et (t[fin]<Tmp) faire
t[fin+1] <-- t[fin]
fin <-- fin-1
fin tant que
fin decaler

Code en Pascal (mode récursive):

Code:: PROCEDURE TRI (VAR T:TAB; D:INTEGER);
var I,E:Integer;
begin
IF D > 1
THEN
begin
TRI(T,D-1) ;
I:=D-1;
E:=T[D];
WHILE(E<T[I]) AND (I>=1) DO
BEGIN
T[I+1] :=T[I];
I:=I-1;
END;
IF E>=T[I] THEN T[I+1]:=E;
end;
end;