Le tri par insertion - avec explication -

Cette méthode de tri par insertion est très différente de la méthode de tri par sélection.

Le principe de ce tri est donc de considérer que les (i-1) premières cartes,T[1] ,..., T[i-1] sont triées et de placer la ieme carte, T[i], à sa place parmi les (i-1) déjà triées, et ainsi de suite jusqu'à ce que i = N.

Pour placer T[i], on utilise une variable intermédiaire temp pour conserver sa valeur qu'on compare successivement à chaque élément T[i-1],T[i-2],... qu'on déplace vers la droite tant que sa valeur est supérieure à celle de temp. On affecte alors à l'emplacement dans le tableau laissé libre par ce décalage la valeur de temp.

 

/* Procédure de tri par insertion */

procedure triInsertion(entier[] T)

   entier i, k;

   entier temp;

   pour (i de 2 à N en incrémentant de 1) faire

      temp <- T[i];

      k <- i;

      tant que (k > 1 et T[k - 1] > temp) faire

         T[k] <- T[k - 1];

         k <- k - 1;

      fin tant que

   T[k] <- temp;

   fin pour

fin procedure

La comparaison avec les algorithmes -de tri par sélection et de tri bulle- montre que la complexité du tri par insertion est plus fortement dépendante de l'ordre du tableau initial. Nous comptons ici le nombre de comparaisons (qui est le nombre de décalages à un près) :

• Dans le meilleur des cas, le tableau initial est trié et on effectue alors une comparaison à chaque insertion, on effectue donc N-1 comparaisons .
• En moyenne, on montre que le nombre de comparaisons est de :

 

• Dans le pire des cas, les entiers du tableau sont initialement donnés dans l'ordre décroissant. Dans ce cas, on effectue l'échange à chaque comparaison, c'est-à-dire que le nombre d'échanges est alors de :

Contrairement aux tris par sélection et bulle qui nécessitent un nombre constant de comparaisons, le tri par insertion ne conduit qu'à très peu de comparaisons lorsque le tableau initial est presque en ordre. Ce tri a donc de meilleures propriétés.