Tri par insertion
Le tri par insertion, c'est la façon dont la plupart des gens trient une main de cartes : prendre la carte suivante et la glisser à la bonne place parmi les cartes déjà rangées. Il est lent sur les longues listes aléatoires, mais très rapide sur les listes courtes ou presque triées, et c'est pourquoi les vraies bibliothèques de tri l'utilisent encore.
Le principe
Gardez le début de la liste trié. Au départ, cette partie triée n'est que la première valeur. Prenez la valeur suivante et comparez-la à celle qui la précède. Si celle-ci est plus grande, échangez-les et comparez à nouveau, une place plus loin vers le début. Arrêtez-vous quand la valeur précédente n'est pas plus grande, ou quand la valeur atteint le début. La partie triée a grandi d'une valeur. Recommencez avec chaque valeur jusqu'à la fin.
Un exemple
Prenons 5, 1, 4, 2, 8. Le passage 1 prend 1 : 5 est plus grand, on les échange, et 1 arrive en tête : 1, 5, 4, 2, 8. Le passage 2 prend 4 : il s'échange avec 5, puis s'arrête à 1 : 1, 4, 5, 2, 8. Le passage 3 prend 2 : il s'échange avec 5 puis avec 4, puis s'arrête à 1 : 1, 2, 4, 5, 8. Le passage 4 prend 8, déjà plus grand que 5, donc une comparaison suffit. Cela fait 7 comparaisons et 4 échanges. Le tri à bulles demande 9 comparaisons sur la même liste, le tri par sélection 10.
Les échanges égalent les inversions
Une inversion est une paire de valeurs dans le mauvais ordre. Échanger deux voisins mal ordonnés supprime exactement une inversion, et le tri par insertion n'échange que de tels voisins. Il fait donc exactement autant d'échanges que la liste de départ compte d'inversions, autant que le tri à bulles. Chaque passage fait aussi au plus une comparaison qui ne mène pas à un échange : celle qui l'arrête. Les comparaisons valent donc les inversions plus au plus n − 1.
Adaptatif : rapide quand la liste est presque triée
Comme le travail vaut le nombre d'inversions plus environ n, le tri par insertion est rapide dès qu'il y a peu d'inversions. Une liste triée demande n − 1 comparaisons et aucun échange. Une liste où chaque valeur n'est qu'à quelques places de la sienne prend un temps proche de n. Seule une liste loin d'être triée, comme une liste inversée avec n(n − 1)/2 inversions, prend un temps proportionnel à n². Sur une liste aléatoire, la moyenne est d'environ n²/4 échanges.
Où il est utilisé
Le tri par insertion est stable, ne demande aucune mémoire supplémentaire et a très peu de surcoût. Sur des listes courtes, il bat des algorithmes plus rapides sur le papier. Beaucoup de tris de bibliothèque, comme Timsort en Python et Java et l'introsort utilisé en C++, passent au tri par insertion pour les petits morceaux de la liste, en général jusqu'à quelques dizaines de valeurs. Il convient aussi aux données qui arrivent une valeur à la fois, car chaque nouvelle valeur peut être insérée dès son arrivée.
À vous d'essayer
Ouvrez l'application et appuyez sur Lecture, ou sur Étape pour avancer d'une comparaison à la fois. La valeur en cours d'insertion a sa propre couleur, la valeur à laquelle elle est comparée est mise en évidence, et la partie triée est verte. Contrairement au tri à bulles et au tri par sélection, la partie verte n'est pas définitive : une valeur plus petite venue plus tard peut encore s'y glisser. Essayez une liste presque triée pour voir combien les passages sont courts, puis une liste inversée.
Questions fréquemment posées
Quelle est la complexité en temps du tri par insertion ?
O(n²) dans le pire cas et en moyenne, et O(n) dans le meilleur cas, une liste déjà triée. Plus précisément, il prend un temps proportionnel à n plus le nombre d'inversions. Il ne demande que O(1) de mémoire supplémentaire.
Quelle différence entre le tri par insertion et le tri par sélection ?
Le tri par sélection parcourt toute la partie non triée pour trouver la plus petite valeur : il fait donc toujours n(n − 1)/2 comparaisons, mais peu d'échanges. Le tri par insertion prend la valeur suivante telle qu'elle vient et ne la fait reculer qu'autant que nécessaire : il fait donc moins de comparaisons, surtout sur les listes presque triées, mais plus d'échanges.
Qu'est-ce que le tri par insertion binaire ?
Une variante qui trouve la place de la nouvelle valeur par une recherche dichotomique dans la partie triée, ce qui demande environ log n comparaisons au lieu de n au plus. Il faut quand même décaler les valeurs pour faire de la place, donc le nombre de déplacements, et le pire cas en O(n²), restent les mêmes.
Le tri par insertion est-il stable ?
Oui. Une valeur ne recule qu'au-delà de valeurs strictement plus grandes, donc les valeurs égales gardent leur ordre d'origine.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer le tri par insertion