Tri par sélection
Trier un tableau en cherchant, à chaque passe, le minimum de la partie non triée pour l'échanger avec sa première case : déroulé, nombre de comparaisons et d'échanges, stabilité.
- 25 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Tri par sélection : de quoi s'agit-il ?
Voir la réponse
Tri qui, à chaque passe, cherche le plus petit élément de la partie non triée et l'échange avec la première case de cette partie.
Après k passes, les k premières cases contiennent leurs valeurs définitives et ne bougent plus : la partie triée grandit d'une case par passe.
Quel est le tableau après la première passe du tri par sélection sur
[6, 2, 9, 1, 5]?[1, 2, 9, 6, 5][2, 6, 9, 1, 5][1, 6, 2, 9, 5][2, 1, 6, 5, 9]
Voir la réponse
[1, 2, 9, 6, 5]Le minimum, 1, est à l'indice 3 : il est échangé avec la case 0, qui contenait 6. Le 6 part donc en position 3 et les autres cases ne bougent pas. Décaler les cases pour glisser le 1 en tête, au lieu de l'échanger, donnerait
[1, 6, 2, 9, 5].Dans le tri par sélection, la boucle intérieure commence à l'indice … et cherche l'indice … de la partie non triée.
Voir la réponse
Dans le tri par sélection, la boucle intérieure commence à l'indice i + 1 et cherche l'indice du minimum de la partie non triée.
On part de
m = i: la case i est déjà candidate, et la boucle ne compare que les cases suivantes àt[m].Passe : de quoi s'agit-il ?
Voir la réponse
Un tour complet de la boucle extérieure d'un tri : ici, une recherche du minimum suivie d'un échange.
Un tableau de n valeurs demande n − 1 passes : quand n − 1 cases sont à leur place, la dernière l'est aussi.