Tri par insertion

Exemple du tri par insertion utilisant une liste de nombres aléatoires

En informatique, le tri par insertion est un algorithme de tri classique, que la plupart des personnes utilisent naturellement pour trier des cartes à jouer : prendre les cartes mélangées une à une sur la table, et former une main en insérant chaque carte à sa place.

En général, le tri par insertion est beaucoup plus lent que d'autres algorithmes comme le tri rapide (ou quicksort) et le tri fusion pour traiter de grandes séquences, car sa complexité asymptotique est quadratique.

Le tri par insertion est cependant considéré comme le tri le plus efficace sur des entrées de petite taille. Il est aussi très rapide lorsque les données sont déjà presque triées. Pour ces raisons, il est utilisé en pratique en combinaison avec d'autres méthodes comme le tri rapide.

En programmation informatique, on applique le plus souvent ce tri à des tableaux. La description et l'étude de l'algorithme qui suivent se restreignent à cette version, tandis que l'adaptation à des listes est considérée plus loin.

Description de l'algorithme

Illustration graphique du tri par insertion.

Dans l'algorithme, on parcourt le tableau à trier du début à la fin. Au moment où on considère le i-ème élément, les éléments qui le précèdent sont déjà triés. Pour faire l'analogie avec l'exemple du jeu de cartes, lorsqu'on est à la i-ème étape du parcours, le i-ème élément est la carte saisie, les éléments précédents sont la main triée et les éléments suivants correspondent aux cartes encore mélangées sur la table.

L'objectif d'une étape est d'insérer le i-ème élément à sa place parmi ceux qui précèdent. Il faut pour cela trouver où l'élément doit être inséré en le comparant aux autres, puis décaler les éléments afin de pouvoir effectuer l'insertion. En pratique, ces deux actions sont fréquemment effectuées en une passe, qui consiste à faire « remonter » l'élément au fur et à mesure jusqu'à rencontrer un élément plus petit.

Voici une description en pseudo-code de l'algorithme présenté. Les éléments du tableau T sont numérotés de 0 à n-1. n est la taille du tableau.

  procédure tri_insertion(tableau T, entier n)
      pour i de 1 à n - 1
          # mémoriser la valeur de T[i]
          x ← T[i]
          # déplacer d'un cran  vers la droite les éléments de T[0]..T[i-1] qui sont plus grands que lui
          j ← i
          tant que j > 0 et T[j - 1] > x
              T[j] ← T[j - 1]
              j ← j - 1
          fin tant que
          # et mettre la valeur dans le "trou" que ça a laissé
          T[j] ← x
     fin pour
  fin procédure

Le tri par insertion est un tri stable (conservant l'ordre d'apparition des éléments égaux) et un tri en place (il n'utilise pas de tableau auxiliaire).

L'algorithme a la particularité d'être online, c'est-à-dire qu'il peut recevoir la liste à trier élément par élément sans perdre en efficacité.

Other Languages