Tri par insertion

Le tri par insertion considère chaque élément du tableau et l'insère à la bonne place parmi les éléments déjà triés. Ainsi, au moment où on considère un élément, les éléments qui le précèdent sont déjà triés, tandis que les éléments qui le suivent ne sont pas encore triés.

Pour trouver la place où insérer un élément parmi les précédents, il faut le comparer à ces derniers, et les décaler afin de libérer une place où effectuer l'insertion. Le décalage occupe la place laissée libre par l'élément considéré. En pratique, ces deux actions s'effectuent en une passe, qui consiste à faire « remonter » l'élément au fur et à mesure jusqu'à rencontrer un élément plus petit.

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é.

Voici les étapes de l'exécution du tri par insertion sur le tableau [6, 5, 3, 1, 8, 7, 2, 4]. Le tableau est représenté au début et à la fin de chaque itération.

Illustration graphique du tri par insertion.

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

  procédure tri_insertion(tableau T)
       pour i de 1 à taille(T) - 1
            # mémoriser T[i] dans x
            x ← T[i]                            
            # décaler les éléments T[0]..T[i-1] qui sont plus grands que x, en partant de T[i-1]
            j ← i                               
            tant que j > 0 et T[j - 1] > x
                     T[j] ← T[j - 1]
                     j ← j - 1
            # placer x dans le "trou" laissé par le décalage
            T[j] ← x                            

La complexité du tri par insertion est Θ(n²) dans le pire cas et en moyenne, et linéaire dans le meilleur cas. Plus précisément :

1. Dans le pire cas, atteint lorsque le tableau est trié à l'envers, l'algorithme effectue de l'ordre de n²/2 affectations et comparaisons[2] ;
2. Si les éléments sont distincts et que toutes leurs permutations sont équiprobables (ie avec une distribution uniforme), la complexité en moyenne de l'algorithme est de l'ordre de n²/4 affectations et comparaisons[2] ;
3. Si le tableau est déjà trié, il y a n-1 comparaisons et au plus n affectations.

La complexité du tri par insertion reste linéaire si le tableau est presque trié (par exemple, chaque élément est à une distance bornée de la position où il devrait être, ou bien tous les éléments sauf un nombre borné sont à leur place). Dans cette situation particulière, le tri par insertion surpasse d'autres méthodes de tri : par exemple, le tri fusion et le tri rapide (avec choix aléatoire du pivot) sont tous les deux en ${\displaystyle \Theta (n\,\log n)}$ même sur une liste triée.

En pratique, sur les petites entrées, en dessous d'une taille critique K (qui dépend de l'implémentation et de la machine utilisée), les algorithmes de tri en ${\displaystyle O(n\,\log n)}$ basés sur la méthode « diviser pour régner » (tri fusion, tri rapide) sont moins efficaces que le tri par insertion. Dans ce type d'algorithmes, plutôt que de diviser récursivement l'entrée jusqu'à avoir des sous-problèmes élémentaires de taille 1 ou 2, on peut s'arrêter dès que les sous-problèmes ont une taille inférieure à K et les traiter avec le tri par insertion.

Pour le cas particulier du tri rapide, une variante plus efficace existe[3] :

• exécuter d'abord le tri rapide en ignorant simplement les sous-problèmes de taille inférieure à K ;
• faire un tri par insertion sur le tableau complet à la fin, ce qui est rapide car la liste est déjà presque triée.

• (en) Illustration dynamique du tri par insertion