- Comparées
- Minimum jusqu'ici
- Échangées
- En place
Tri par sélection
Le tri par sélection construit la liste triée par le début. Chaque passage parcourt les valeurs pas encore triées, retient la plus petite et l'amène par un échange en première position non triée. Lancez le tri à la vitesse voulue, ou avancez d'une comparaison à la fois, et suivez les compteurs de comparaisons, d'échanges et de passages. Appuyez sur Lecture pour regarder le tri, ou sur Étape et Retour pour avancer d'une comparaison à la fois. Faites glisser le curseur d'étapes pour aller n'importe où. Les tuiles comptent les comparaisons, les échanges et les passages. Choisissez le nombre de barres, leur ordre de départ, ou saisissez vos propres nombres. Quand le tableau est sélectionné, les flèches avancent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.
Comment ça marche
- Choisissez le nombre de barres et leur ordre de départ : aléatoire, presque trié, inversé ou avec peu de valeurs distinctes. Ou saisissez vos propres nombres.
- Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer d'une comparaison à la fois. Faites glisser le curseur d'étapes pour aller n'importe où dans le tri.
- Regardez la plus petite valeur trouvée changer au fil du parcours, puis l'échange qui la met en place à la fin de chaque passage.
Comment fonctionne le tri par sélection
Examinez chaque valeur de la liste et retenez la plus petite. Échangez-la avec la première valeur : la première position est maintenant définitive. Faites ensuite de même pour le reste de la liste, en commençant une position plus loin. Après n − 1 passages, chaque valeur est en place, la dernière l'étant d'office.
Beaucoup de comparaisons, peu d'échanges
Le parcours ne s'arrête jamais plus tôt, car ce n'est qu'après avoir examiné toutes les valeurs restantes qu'il sait laquelle est la plus petite. Le tri par sélection fait donc exactement n(n − 1)/2 comparaisons pour n valeurs, que la liste soit triée, inversée ou aléatoire. En contrepartie, il fait au plus n − 1 échanges, un par passage. C'est donc un bon choix quand déplacer une valeur coûte bien plus que comparer deux valeurs.
Questions fréquemment posées
Comment fonctionne le tri par sélection ?
Il sélectionne à chaque fois la plus petite valeur pas encore triée et l'amène par un échange en première position non triée. Après le passage k, les k premières positions contiennent les k plus petites valeurs dans l'ordre.
Combien de comparaisons et d'échanges fait le tri par sélection ?
Toujours n(n − 1)/2 comparaisons pour n valeurs : 45 pour 10 valeurs, 780 pour 40. Le nombre d'échanges est d'au plus n − 1, un par passage, et moins quand la plus petite valeur est déjà en place.
Pourquoi une liste triée prend-elle autant de temps qu'une liste inversée ?
Parce que chaque passage doit examiner toutes les valeurs restantes pour être sûr d'avoir trouvé la plus petite. Contrairement au tri à bulles et au tri par insertion, le tri par sélection ne peut pas voir d'après ses comparaisons que la liste est déjà triée.
Le tri par sélection est-il stable ?
Pas sous sa forme habituelle. Un échange peut faire passer une valeur par-dessus une valeur égale : dans 2, 2, 1, le premier 2 est échangé avec le 1 et se retrouve derrière le second 2. Une version qui décale les valeurs au lieu de les échanger est stable, au prix de plus de déplacements.
Mes nombres sont-ils envoyés quelque part ?
Non. Le tri s'exécute dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur