le Tri par INSERTION

Le tri par insertion séquentielle est un algorithme de tri simple et intuitif, souvent comparé à la manière dont on trie des cartes à jouer. Le principe consiste à parcourir le tableau de gauche à droite en considérant qu’une partie est déjà triée, puis à insérer chaque nouvel élément à sa position correcte dans cette zone triée. Pour cela, l’algorithme mémorise l’élément courant dans une variable, décale vers la droite tous les éléments plus grands, puis place l’élément à insérer au bon endroit. Ce tri est particulièrement efficace lorsque le tableau est déjà presque trié, car le nombre de décalages devient faible. En revanche, si les éléments sont dans l’ordre inverse, le tri peut nécessiter un grand nombre de déplacements, ce qui mène à une complexité quadratique.

Le tri par insertion parcourt le tableau de gauche à droite en considérant qu’une partie est déjà triée. À chaque étape, on prend l’élément courant et on l’insère à sa bonne place dans la zone triée en décalant vers la droite tous les éléments plus grands.

Algorithme (pseudocode)

algorithme TriInsertion

const N <-- 100 ;

var
  t : tableau[1..N] de Entier;
  i, k, x : entier;

début
  écrire("Lecture des éléments du tableau");

  pour i de 1 à N faire
    écrire("Entrer le ", i, "ème élément : ");
    lire(t[i]);
  fpour

  pour i de 2 à N faire
    x <-- t[i];
    k <-- i - 1;

    tantque (k > 0) et (t[k] > x) faire
      t[k + 1] <-- t[k];
      k <-- k - 1;
    ftantque

    t[k + 1] <-- x;
  fpour

  écrire("Le tableau trié est :");
  pour i de 1 à N faire
    écrire(t[i]);
  fpour
fin.
  

Explication 

1) Objectif

L’objectif est de trier le tableau en ordre croissant en insérant progressivement chaque élément dans une partie déjà triée du tableau.

2) Étapes de fonctionnement

1. On lit les N éléments du tableau.
2. On démarre à i = 2 car un seul élément (t[1]) est déjà trié.
3. On copie l’élément courant dans x (élément à insérer).
4. On compare x avec les éléments à gauche et on décale vers la droite ceux qui sont plus grands.
5. Quand on trouve la bonne position, on insère x dans t[k+1].

3) Remarque (sans sentinelle)

On n’utilise pas de sentinelle : on arrête la boucle dès que k vaut 0 ou dès que t[k] devient inférieur ou égal à x. Ensuite, on place x dans t[k+1].

4) Complexité

• Meilleur cas (tableau déjà trié) : proche de O(n)
• Pire cas (tableau trié à l’envers) : O(n²)
• Mémoire : O(1) (tri en place)