Tri par insertion (Insertion Sort)

Le tri par insertion est un algorithme de tri simple et efficace pour des petites listes ou des listes presque triées. Cet algorithme fonctionne de manière similaire à la façon dont on organise des cartes dans une main en les insérant dans l'ordre souhaité.

Principe du tri par insertion

Le tri par insertion est une méthode de tri utilisée pour organiser une liste d'éléments en les insérant dans un ordre spécifique, souvent du plus petit au plus grand. Ce principe repose sur l'idée de traiter la liste élément par élément, en les insérant au bon endroit dans une portion de liste déjà triée. Au début, la liste est divisée en deux parties : une sous-liste triée et une autre contenant les éléments restants. À chaque étape, le premier élément de la liste non triée est pris, et inséré dans la bonne position parmi les éléments déjà triés.

L'algorithme fonctionne particulièrement bien sur les petites listes ou les listes qui sont déjà en grande partie triées. En effet, sa complexité en temps est de O(n²) dans le pire des cas, mais elle peut être proche de O(n) lorsque les données sont presque dans l'ordre. Chaque insertion dans la partie triée est effectuée en décalant les éléments plus grands d'une position vers la droite, pour faire de la place à l'élément à insérer. Ainsi, le tri par insertion peut être plus rapide que d'autres algorithmes de tri pour les petites collections de données ou celles ayant peu de désordre.

Un autre avantage du tri par insertion est qu'il est un algorithme stable, c'est-à-dire qu'il conserve l'ordre relatif des éléments ayant des valeurs égales. Par exemple, si deux objets partagent la même valeur de tri, leur ordre d'origine restera inchangé après le tri. Cela peut être très utile dans certaines applications où l'ordre initial a une signification. Le tri par insertion étant aussi un algorithme en place, il ne nécessite pas d'espace mémoire supplémentaire important, rendant son utilisation optimale lorsque la mémoire est limitée.

Le tri par insertion est souvent illustré par l'exemple de cartes à jouer : pour organiser un jeu de cartes en main, chaque nouvelle carte tirée est insérée dans la main de sorte à garder l'ordre croissant des valeurs. On balaye ainsi les cartes déjà en main de droite à gauche jusqu'à trouver la bonne position pour insérer la nouvelle carte. Cette démarche intuitive aide à comprendre pourquoi le tri par insertion est une bonne solution pour des données se construisant progressivement, comme lors de l'insertion de nouvelles valeurs.

Enfin, le tri par insertion présente cependant des limites lorsque le volume de données devient très important. Pour des listes longues et complètement désordonnées, d'autres algorithmes de tri plus performants, comme le tri rapide ou le tri par fusion, sont généralement privilégiés. Néanmoins, le tri par insertion reste un choix pertinent pour des scénarios spécifiques, notamment dans des applications embarquées ou temps réel, où l'optimisation de l'espace mémoire et la simplicité de l'algorithme sont des critères importants.

Voici le fonctionnement de cet algorithme étape par étape :

• On commence par supposer que le premier élément de la liste est déjà trié.
• Pour chaque élément suivant, on le compare aux éléments de la partie triée (à sa gauche) en remontant vers le début de la liste.
• Lorsqu'on trouve l'endroit où cet élément doit être inséré (c'est-à-dire entre deux éléments plus petit et plus grand), on le place à cette position et déplace les autres éléments pour lui faire de la place.
• On répète cette opération jusqu'à ce que tous les éléments soient triés.

Algorithme

Voici l'algorithme de la tri par insertion :