Tri par sélection
Le tri par sélection trie une liste comme beaucoup de gens trient une main de cartes : trouver la plus petite, la mettre en premier, puis trouver la plus petite du reste. Il fait beaucoup de comparaisons mais très peu d'échanges, et son temps d'exécution dépend à peine de l'ordre de la liste.
L'idée
Divisez la liste en une partie triée à gauche, vide au départ, et une partie non triée à droite. Parcourez la partie non triée et retenez où se trouve sa plus petite valeur. Échangez cette valeur avec la première valeur non triée : la partie triée a grandi d'une valeur. Recommencez jusqu'à ce qu'il ne reste qu'une valeur, qui est forcément la plus grande.
Un exemple
Prenez 5, 1, 4, 2, 8. Le premier passage parcourt les cinq valeurs, trouve 1 comme plus petite et l'échange avec 5 : 1, 5, 4, 2, 8. Le deuxième passage parcourt 5, 4, 2, 8, trouve 2 et l'échange avec 5 : 1, 2, 4, 5, 8. Le troisième passage trouve 4 déjà en place, et le quatrième trouve 5 déjà en place : rien ne bouge. Cela fait 4 + 3 + 2 + 1 = 10 comparaisons et seulement 2 échanges. Le tri à bulles a besoin de 4 échanges sur la même liste.
Toujours le même nombre de comparaisons
Pour savoir à coup sûr quelle valeur est la plus petite, le parcours doit examiner toutes les valeurs restantes. Le passage 1 fait n − 1 comparaisons, le passage 2 en fait n − 2, et ainsi de suite jusqu'à 1, soit n(n − 1)/2 au total. Ce nombre ne dépend pas de la liste : une liste triée coûte exactement autant de comparaisons qu'une liste inversée. Le tri par sélection n'a pas d'arrêt anticipé, car un parcours qui trouve la plus petite valeur déjà en tête n'a rien appris sur le reste.
Peu d'échanges
Chaque passage fait au plus un échange, donc le tri par sélection ne fait jamais plus de n − 1 échanges, et il saute l'échange quand la plus petite valeur est déjà en place. Le tri à bulles et le tri par insertion font autant d'échanges qu'il y a de paires mal ordonnées, ce qui peut atteindre environ n²/2. Quand écrire une valeur coûte bien plus cher qu'en lire deux, par exemple sur une mémoire qui s'use à chaque écriture, ce petit nombre d'échanges est un avantage.
Pas stable
Un tri est stable quand les valeurs égales gardent leur ordre d'origine. Le tri par sélection ne l'est pas, car un échange à longue distance peut faire passer une valeur par-dessus une valeur égale. Dans 2, 2, 1, le premier passage échange le premier 2 avec le 1, ce qui donne 1, 2, 2 avec les deux 2 désormais dans l'ordre inverse. Une version qui décale les valeurs intermédiaires au lieu d'échanger est stable, mais elle déplace beaucoup plus de valeurs.
À vous d'essayer
Ouvrez l'application et appuyez sur Lecture, ou sur Étape pour avancer d'une comparaison à la fois. La valeur examinée est mise en évidence, la plus petite valeur trouvée jusqu'ici a sa propre couleur, et chaque passage se termine par un échange vers la partie triée à gauche. Essayez une liste triée et une liste inversée : les comparaisons sont les mêmes, seuls les échanges diffèrent.
Questions fréquemment posées
Quelle est la complexité en temps du tri par sélection ?
O(n²) dans tous les cas : exactement n(n − 1)/2 comparaisons pour n valeurs, quel que soit leur ordre. Il fait au plus n − 1 échanges et n'a besoin que de O(1) mémoire supplémentaire.
Quelle est la différence entre le tri par sélection et le tri à bulles ?
Le tri à bulles échange des voisins au fur et à mesure et peut s'arrêter tôt dès qu'un passage ne fait aucun échange. Le tri par sélection retient seulement où se trouve la plus petite valeur et fait un seul échange à la fin de chaque passage. Le tri par sélection fait moins d'échanges ; le tri à bulles est plus rapide sur les listes presque triées.
Le tri par sélection est-il stable ?
Non. Un échange peut faire passer une valeur par-dessus une autre valeur égale, donc des valeurs égales peuvent changer d'ordre. On peut le rendre stable en décalant les valeurs au lieu de les échanger, ce qui demande plus de déplacements.
Quel est le lien entre le tri par tas et le tri par sélection ?
Le tri par tas est un tri par sélection avec une façon plus rapide de trouver la valeur suivante : il garde la partie non triée dans un tas, si bien que chaque sélection prend environ log n étapes au lieu d'un parcours complet. Le total descend ainsi à O(n log n).
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer le tri par sélection