Vous connaissez déjà le tri par insertion, de complexité O(nlogn) dans le meilleur des cas et O(n2) dans le pire. Vous savez que c’est le tri utilisé pour ordonner ses cartes au tarot. Mais connaissez-vous sa variante faisant appel à la mémoire ?

Dans la suite, je vais illustrer les exemples à l’aide de ma liste fétiche initiale (I) d’entiers. Vous remarquerez que cette liste est partiellement déjà triée :

Liste initiale : 0 – 1 – 2 – 4 – 5 – 6 – 3 – 9 – 8 – 7

Le principe du tri par insertion est de partir de la liste initiale (I), d’en prendre le premier élément, puis de l’insérer dans une seconde liste (S) à la bonne place. Pour le premier élément, c’est assez simple de trouver sa bonne place. Pour déterminer la bonne place des éléments suivants, on parcours la seconde liste en comparant l’élément à insérer avec les éléments déjà placés. On est à la bonne place lorsque l’item déjà placé est plus grand que l’item à traiter. Il suffit alors d’insérer l’item, d’où le nom de l’algorithme. On recommence cette opération tant qu’il reste des éléments dans la liste initiale.

Les optimisations de ces algorithmes se basent principalement sur les hypothèses qu’on peut formuler sur les données initiales. Ici, on va partir du principe que les listes sont partiellement (voire entièrement) triées. Dans l’algorithme, au lieux de tenter d’insérer l’élément courant au début de la liste, on va chercher à l’insérer à la même position que l’item précédent. Il faudra donc garder en mémoire cette position, d’où le nom de la variante. Si l’item en place est plus petit, on essaie une position plus haute. Si l’item est plus grand alors on essaie une position plus basse. On a trouvé la bonne position lorsque la tendance s’inverse.

Prenons un exemple. Disons que nous avons déjà trié une partie de la liste et que nous somme dans la position suivante :

S : 0 – 1 – 2 – 4
I : 5 – 6 – 3 – 9 – 8 – 7

Le prochain élément à traiter est donc 5. Le dernier élément traité a été inséré à la position 3 (la première position est zéro par convention). Du coup, on va essayer d’insérer 5 à cette position 4. On voit que 4 est plus grand que l’item en place. On va donc essayer de l’insérer plus haut. On essaie donc à la position 5. Ici, on est dans le cas particulier, mais fréquent, où on se retrouve à la fin de la liste. On peut donc insérer l’item. Cette variante aura donc permis, ici, d’insérer l’item en une seule comparaison. Imaginez le gain avec une liste de 10000 éléments.

Allons plus loin pour voir ce qui se passe pour l’item 3, qui rompt la monotonie de la liste :

S : 0 – 1 – 2 – 4 – 5 – 6
I : 3 – 9 – 8 – 7

On va donc essayer d’insérer l’élément 3 à la position 6. On constate qu’il faut essayer à une position plus basse. Et, si vous avez bien compris, cela nous emmène jusqu’à la position 3 :

S : 0 – 1 – 2 – 4 – 5 – 6/(3) : plus bas
S : 0 – 1 – 2 – 4 – 5/(3) – 6 : plus bas
S : 0 – 1 – 2 – 4/(3) – 5 – 6 : plus bas
S : 0 Р1 Р2/(3) Р4 Р5 Р6 : rupture dans la monotonie donc position trouv̩e

Si vous avez suivi ce raisonnement, vous pouvez vous dire qu’on peut aller encore plus en essayant d’insérer les éléments à la fin, puisque la liste initiale est partiellement triée. Et vous auriez raison. Si vous êtes capables de prédire que votre liste est quasi triée, la complexité de votre algorithme tombe en O(n) et vous ne pourrez pas faire mieux. Ca revient presque à faire une banale inversion de liste.

Mais revenons à ma liste préférée. Vous constatez que les derniers éléments sont tous décroissants. C’est une situation assez courante. Avec l’hypothèse que je peux tomber sur ce cas, je vais donc bien chercher où insérer à partir de la dernière position et non à la fin. Disons qu’on en est juste après l’insertion de l’élément 8. On va donc traiter l’élément 7 :

S : 0 – 1 – 2 – 3 – 4 – 5 – 6 – 8 – 9
I : 7

S : 0 – 1 – 2 – 3 – 4 – 5 – 6 – 8/(7) – 9 : plus bas
S : 0 Р1 Р2 Р3 Р4 Р5 Р6/(7) Р8 Р9 : rupture dans la monotonie donc position trouv̩e

Ici, ce n’est peut être pas le meilleur exemple, car on était à la fin, mais on voit qu’on gagner déjà des étapes.

Ce qu’il faut retenir, c’est que l’algorithme à utiliser dépend grandement des informations que vous possédez sur les données à trier.