Le tri par insertion est comparable au tri par sélection vu dans le TP2

On considère une tableau L d'éléments comparables que l'on trie selon le protocole suivant.

• On classe au fur et à mesure de l'avancée dans le tableau :
  • si le tableau n’a qu’un seul élément il est déjà trié,
  • sinon on prend le deuxième et on le compare au premier pour les mettre dans le bon ordre.
• Si on suppose les i premiers éléments déjà classés on prend le (i + 1)-ème que l’on compare, par exemple en descendant à partir de la position i, jusqu’à trouver, ou pas, un plus petit que lui et l'insérer alors à la bonne place.

FONCTION tri_par_insertion
ENTRÉE: tableau_a_trier, le tableau à trier
La fonction ne renvoie rien, le tableau est trié en place
DÉBUT
  soit n la longueur de tableau_a_trier
  POUR i allant de 1 à n - 1 FAIRE
    soit item l'élément de rang i dans tableau_a_trier
    soit j = i
    TANT QUE j > 0 et l'élément de rang j-1 supérieur à item FAIRE
      copier l'item de rang j-1 au rang j
      j passe à j-1
    FIN
    copier item au rang j
  FIN
FIN

Ici, le tri se fait en place, ce qui est une bonne chose du point de vue de l'utilisation de la mémoire. On peut apporter des améliorations pour limiter le nombre de comparaisons ou d'échanges, mais cela ne change pas le principe d’insertion : il y a deux boucles imbriquées, ici une boucle globale en for et à l'intérieur une boucle en while.

On prouvera plus tard la correction du programme et on étudiera sa complexité.

En profitant du fait qu'au moment de chaque insertion, le début de liste est déjà trié, on peut procéder à une insertion dichotomique selon l'algorithme qui suit :

FONCTION recherche_rang_insertion
ENTRÉES
    L: un tableau
    a, b: deux indices de L, a <= b. L[a:b] est trié dans l'ordre croissant
    e: un élément de même nature que ceux de L
SORTIE
    l'indice a <= i <= b auquel il faudrait insérer e pour respecter l'ordre
DÉBUT
    TANT QUE a != b RÉPÉTER
        indice_milieu est (a + b) // 2
        m est la valeur de L en indice_milieu
        SI m <= e ALORS
            continuer avec la zone [indice_milieu + 1 : b]
        SINON
            continuer avec la zone [a:indice_milieu]
        FIN
    FIN
    RENVOYER a
FIN

On montre que la complexité dans le pire des cas du tri avec insertion dichotomique est en $n\,\ln(n)$.