Tri par insertion

Complexité en temps
Problèmes liés	Algorithme de tri,tri stable(en),tri par comparaison,adaptive sort(en),algorithme en place,algorithme en ligne
Structures des données	Tableau,insert(d)
À l'origine de	Timsort
Pire cas
Moyenne
Meilleur cas
Pire cas

Eninformatique,letri par insertionest unalgorithme de triclassique. La plupart des personnes l'utilisent naturellement pour trier descartes à jouer^[1].

C'est untri par file de prioritéen utilisant l'implémentation par tableau trié des files de priorité^[2].

En général, le tri par insertion est beaucoup plus lent que d'autres algorithmes comme letri rapide(ouquicksort) et letri fusionpour traiter de grandes séquences, car sacomplexitéasymptotique est quadratique.

Le tri par insertion est cependant considéré comme l'algorithme le plus efficace sur des entrées de petite taille. Il est aussi efficace 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 letri rapide.

Enprogrammation informatique,on applique le plus souvent ce tri à destableaux.La description et l'étude de l'algorithme qui suivent se restreignent à cette version, tandis que l'adaptation à deslistesest considérée plus loin.

Description

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 untri stable(conservant l'ordre d'apparition des éléments égaux) et untri en place(il n'utilise pas de tableau auxiliaire).

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

Exemple

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.

i = 1:

6

5

3

1

8

7

2

4

⟶

5

6

3

1

8

7

2

4

i = 2:

5

6

3

1

8

7

2

4

⟶

3

5

6

1

8

7

2

4

i = 3:

3

5

6

1

8

7

2

4

⟶

1

3

5

6

8

7

2

4

i = 4:

1

3

5

6

8

7

2

4

⟶

1

3

5

6

8

7

2

4

i = 5:

1

3

5

6

8

7

2

4

⟶

1

3

5

6

7

8

2

4

i = 6:

1

3

5

6

7

8

2

4

⟶

1

2

3

5

6

7

8

4

i = 7:

1

2

3

5

6

7

8

4

⟶

1

2

3

4

5

6

7

8

Pseudo-code

Voici une description enpseudo-codede l'algorithme présenté. Les éléments du tableauT(de taillen) sont numérotés de 0 àn-1.

procéduretri_insertion(tableauT)

pouride1à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 quej > 0etT[j - 1] > x
T[j] ← T[j - 1]
j ← j - 1

# placer x dans le "trou" laissé par le décalage
T[j] ← x

Complexité

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:

Dans le pire cas, atteint lorsque le tableau est trié à l'envers, l'algorithme effectue de l'ordre den²/2affectationset comparaisons^[3];
Si les éléments sont distincts et que toutes leurspermutationssontéquiprobables(ie avec unedistribution uniforme), lacomplexité en moyennede l'algorithme est de l'ordre den²/4 affectations et comparaisons^[3];
Si le tableau est déjà trié, il y an-1 comparaisons et au plusnaffectations.

La complexité du tri par insertion reste linéaire si le tableau estpresquetrié (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, letri fusionet letri rapide(avec choix aléatoire du pivot) sont tous les deux en $\Theta (n\,\log n)$ même sur une liste triée.

Variantes et optimisations

Optimisations pour les tableaux

Plusieurs modifications de l'algorithme permettent de diminuer le temps d'exécution, bien que la complexité reste quadratique.

On peut optimiser ce tri en commençant par un élément au milieu de la liste puis en triant alternativement les éléments après et avant. On peut alors insérer le nouvel élément soit à la fin, soit au début des éléments triés, ce qui divise par deux le nombre moyen d'éléments décalés. Il est possible d'implémenter cette variante de sorte que le tri soit encore stable.
En utilisant unerecherche par dichotomiepour trouver l'emplacement où insérer l'élément, on peut ne faire que $O(n\,\log n)$ comparaisons. Le nombre d'affectations reste en O(n²).
L'insertion d'un élément peut être effectuée par une série d'échangesplutôt que d'affectations. En pratique, cette variante peut être utile dans certainslangages de programmation(par exempleC++), où l'échange destructures de donnéescomplexes estoptimisé,alors que l'affectation provoque l'appel d'unconstructeur de copie.

Letri de Shellest une variante du tri par insertion qui améliore sa complexité asymptotique, mais n'est pas stable.

Tri par insertion sur des listes

Le principe du tri par insertion peut être adapté à deslistes chaînées.Dans ce cas, le déplacement de chaque élément peut se faire en temps constant (une suppression et un ajout dans la liste). Par contre, le nombre de comparaisons nécessaires pour trouver l'emplacement où insérer reste de l'ordre den²/4,la méthode de recherche par dichotomie ne pouvant pas être appliquée à des listes.

Combinaison avec d'autres tris

En pratique, sur les petites entrées, en dessous d'une taille critiqueK(qui dépend de l'implémentation et de la machine utilisée), les algorithmes de tri en $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 àKet les traiter avec le tri par insertion.

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

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.