Algorithme de tri par insertion☘
tab est un tableau d'éléments porteur d'une relation d'ordre,
c'est-à-dire d'éléments que l'on peut comparer entre eux.
On désigne par n la taille du tableau tab donc les éléments de tab sont
numérotés de 0 à n-1.
Définition
On appelle « tri par insertion » un algorithme de tri d’un tableau
tab qui, dans chaque sous-tableau tab[..i], insère correctement
tab[i] par décalages à droite.
Algorithme de tri par insertion☘
Cet algorithme nécessite d’être décomposé, avec l’insertion d’un élément dans un sous-tableau trié d’une part et le tri qui fait appel à ces insertions d’autre part.
Pour i variant de 1 à n-1 :
Insérer tab[i] dans tab[..i]
Fin Pour
Il reste à définir l'instruction Insérer dans un tableau tab indexé de 0
à n-1 tel que les éléments de tab[..i-1] sont triés par ordre croissant.
temp ← tab[i] # Mise en mémoire du dernier élément
# Décalage vers la droite des éléments de tab[0..i-1] qui sont plus grands que
# temp en partant de l'avant-dernier c'est-à-dire de tab[i-1]
j ← i
Tant que (j > 0) et (tab[j-1] > temp) :
tab[j] ← tab[j-1]
j ← j-1
Fin Tant que
tab[j] ← temp # On place temp dans le "trou"
Application à un exemple☘
On considère le tableau suivant, à trier selon l'algorithme de tri par insertion.
tab = |
14 | 12 | 17 | 11 | 18 | 15 | 13 |
A noter
D'un point de vue informatique, on s'interdit de créer un tableau intermédiaire : c'est un tri par « effet de bord ».
-
On se retreint au sous-tableau
tab[..1]:tab=14 12 17 11 18 15 13 L'élément d'indice
1(la carte de valeur 12) est mis à sa place danstab[..1]:tab=12 14 17 11 18 15 13 -
On poursuit avec le sous-tableau
tab[..2]:tab=12 14 17 11 18 15 13 L'élément d'indice
2(la carte de valeur 17) est mis à sa place danstab[..2]:tab=12 14 17 11 18 15 13 -
On continue avec le sous-tableau
tab[..3]:tab=12 14 17 11 18 15 13 L'élément d'indice
3(la carte de valeur 11) est mis à sa place danstab[..3]:tab=11 12 14 17 18 15 13 -
On considère à présent le sous-tableau
tab[..4]:tab=11 12 14 17 18 15 13 L'élément d'indice
4est inséré danstab[..4]:tab=11 12 14 17 18 15 13 -
Dans le sous-tableau
tab[..5]:tab=11 12 14 17 18 15 13 On insère l'élément d'indice
5:tab=11 12 14 15 17 18 13 -
On termine avec
tab[..6]:tab=11 12 14 15 17 18 13 dans lequel on insère l'élément d'indice
6:tab=11 12 13 14 15 17 18