N.S.I. WorkSpace Compétence,Notions,P-Th-G,Première G2 – Tris par insertion, par sélection

G2 – Tris par insertion, par sélection

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 tableau
Algorithme 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
    FIN

Déroulé du tri par insertion sur un exemple :

Animation du tri par insertion