1 – Le tri par insertion
Le tri par insertion est le mode de tri « naturel ».
Son principe est le suivant :
Comparer la valeur de l’élément d’index 1 du tableau avec la valeur de l’élément d’index 0 :
si la valeur de l’élément d’index 1 du tableau est inférieure à la valeur de l’élément d’index 0, alors permuter ces deux éléments.
Comparer la valeur de l’élément d’index 2 du tableau avec la valeur de l’élément d’index 1 :
si la valeur de l’élément d’index 2 du tableau est inférieure à la valeur de l’élément d’index 1, alors :
- permuter ces deux éléments ;
- puis comparer la valeur de l’élément d’index 1 du tableau avec la valeur de l’élément d’index 0 :
--- si la valeur de l’élément d’index 1 du tableau est inférieure à la valeur de l’élément d’index 0, alors permuter ces deux éléments.
Comparer la valeur de l’élément d’index 3 du tableau avec la valeur de l’élément d’index 2 :
- si la valeur de l’élément d’index 3 du tableau est inférieure à la valeur de l’élément d’index 2, alors
--- permuter ces deux éléments.
--- puis comparer la valeur de l’élément d’index 2 du tableau avec la valeur de l’élément d’index 1 :
----- si la valeur de l’élément d’index 2 du tableau est inférieure à la valeur de l’élément d’index 1, alors :
-------- permuter ces deux éléments.
-------- Puis comparer la valeur de l’élément d’index 1 du tableau avec la valeur de l’élément d’index 0 :
----------- si la valeur de l’élément d’index 1 du tableau est inférieure à la valeur de l’élément d’index 0, alors permuter ces deux éléments.
Et ainsi de suite jusqu'au dernier élément du tableauAlgorithme de tri par insertion
soit T un tableau de valeurs à trier
DEBUT
PARCOURIR le tableau à partir du deuxième élément jusqu'au dernier.
A chaque étape du parcours :
TANT QUE l'élément au niveau duquel on est rendu dans le parcours est
inférieur à celui qui le précède ET TANT QU'on n'a pas atteint le
premier élément du tableau, ALORS :
PERMUTER ces deux éléments
FIN TANT QUE
FINDéroulé du tri par insertion sur un exemple :
