Programmez par plaisir! 02-09-2014
13:38
Prog-Info > C++ > Tri et Recherche > Tri par insertion. Sommaire

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 :

730 196
370 196
037 196
013 796
013 796
013 799
013 779
013 679

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...

Le tri par sélection Le tri par création
[Plan Plan] [A propos A Propos] [ 1439035 ]
Copyright ©2002-2009 Prog-info Tous droits réservés.