Tri par insertion

Algorithme quadratique, T(n) = O(n²), en moyenne et dans le pire des cas, stable et en place. C'est le plus rapide et le plus utilisé pour un petit nombre de valeurs à trier. Cette méthode de tri est très différente de la méthode de tri par sélection et s'apparente à celle utilisée pour trier ses cartes dans un jeu : on prend une carte, tab[1], puis la deuxième, tab[2], que l'on place en fonction de la première, ensuite la troisième tab[3] que l'on insère à sa place en fonction des deux premières et ainsi de suite. Le principe général est donc de considérer que les (i-1) premières cartes, tab[1],..., tab[i-1] sont triées et de placer la i^e carte, tab[i], à sa place parmi les (i-1) déjà triées, et ce jusqu'à ce que i = N.

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

La procédure de tri par insertion est la suivante :

procedure triInsertion(entier[] tab)

   entier i, k;

   entier tmp;

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

      tmp <- tab[i];

      k <- i;

      tant que (k > 1 et tab[k - 1] > tmp) faire

         tab[k] <- tab[k - 1];

         k <- k - 1;

      fin tant que

   tab[k] <- tmp;

   fin pour

fin procedure