Prog-Info > C++ > Tri et Recherche > Tri par insertion.

Le tri par insertion

Le but de cet algorithme est de prendre les éléments un par un en commençant en début de tableau et de les classer par rapport aux éléments se trouvant à leur gauche. L'élément 0 est par définition classé. L'élément 1 est comparé avec l'élément 0, si il est inférieur alors on échange les deux éléments. Ensuite on passe à l'élément 2 : il est d'abord comparé à l'élément 1. S'il lui est inférieur alors on procède à l'échange, on compare l'élément 1 à l'élément 0 (rappel : l'élément 1 et 2 ont été échangés), on fait l'échange si l'élément 1 est inférieur à l'élément 0 et on passe à l'élément 3. Sinon on passe directement à l'élément 3. etc...
Le problème de cet algorithme est que l'on peut être amené à décaler le dernier élément du tableau en première position, ce qui implique beaucoup d'opérations.

void triParinsertion(int 
        tableau[], int longueur)

        {

           int i, memoire, // 
        memoire:valeur en cours de traitement

               compteur; // 
        indique la partie du tableau à traiter

           bool marqueur; // 
        faut-il continuer les comparaisons?

        

           for(i=1; i<longueur; 
        i++)

           {

              memoire = tableau[i];

              compteur = i-1;

              do

              {

                 marqueur = false;

                 // 
        comparaisons et décalages vers la droite si nécessaire

                 if(tableau[compteur] 
        > memoire)

                 {

                    tableau[compteur+1] 
        = tableau[compteur];

                    compteur--;

                    marqueur 
        = true;

                 }

                 if(compteur 
        < 0) // on évite de dépasser les 
        limites

                    marqueur 
        = false;

              }

              while(marqueur);

           } 

           tableau[compteur+1] = memoire;

           // on a classé le tableau jusqu'à 
        l'indice i

        }

Exemple :
Les grandes étapes de l'algorithme :

7	3	0	1	9	6
3	7	0	1	9	6
0	3	7	1	9	6
0	1	3	7	9	6
0	1	3	7	9	6
0	1	3	7	9	9
0	1	3	7	7	9
0	1	3	6	7	9

Les 3 dernières lignes de l'exemple montrent le détail de l'algorithme. La valeur du dernier élément : 6 étant stockée en mémoire.

Complexité :
Calculons le nombre de passages dans le pire des cas : (n-1)+(n-2)+ ... +2+1 = n*n/2 - n/2.
Cependant en moyenne nous aurons n*n/4 - n/4 passages.
Cet algorithme est intéressant car il peut être utilisée pour classer des valeurs en temps réel : au fur et à mesure qu'elles arrivent...