Ranger les prix du marché
Sur un marché, tu notes les prix d'un kilo de tomates chez cinq vendeurs : 18, 7, 12, 4 et 9 euros.
Tu veux les voir du moins cher au plus cher. Comment fais-tu ? Tu cherches d'abord le plus petit. Tu le mets en premier. Puis tu recommences avec ce qui reste.
C'est exactement le tri par sélection.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Tri | Ranger les valeurs dans un ordre. | Du moins cher au plus cher |
| Croissant | Du plus petit au plus grand. | 4, 7, 9, 12, 18 |
| Passage | Un tour complet de l'algorithme sur ce qui reste à trier. | Le passage 1 place le plus petit |
| Échange | Mettre deux valeurs à la place l'une de l'autre. | La case 0 et la case 3 changent de valeur |
| Zone triée | Le début de la liste, déjà bien rangé. | Après le passage 2 : 4, 7 |
| Variable temporaire | Une variable qui garde une valeur le temps d'un échange. | verre_vide |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : trie de tête
À toi de jouer
À toi : trie de tête
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
D'abord : échanger deux valeurs
Pour placer le plus petit, il faut échanger deux cases. Tu as deux verres : un de jus, un d'eau. Tu ne peux pas les vider l'un dans l'autre.
Il te faut un troisième verre vide. En Python, c'est une variable temporaire. On y met une valeur de côté, le temps de l'échange.
À toi : un échange qui rate
a = 3
b = 5
# Tentative fausse : on écrase a avant de l'avoir gardé.
a = b
b = a
print("a =", a, "et b =", b)
# Les deux valent 5. Le 3 a disparu !
Exemple travaillé : l'échange à trois verres
| Ligne | a | b | verre_vide |
|---|---|---|---|
| Départ | 3 | 5 | - |
| verre_vide = a | 3 | 5 | 3 |
| a = b | 5 | 5 | 3 |
| b = verre_vide | 5 | 3 | 3 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : l'échange qui marche
a = 3
b = 5
verre_vide = a # on met le 3 de côté
a = b # a prend le 5
b = verre_vide # b reprend le 3
print("a =", a, "et b =", b)
# Fais la même chose avec deux cases d'une liste.
prix = [18, 7, 12]
verre_vide = prix[0]
prix[0] = prix[2]
prix[2] = verre_vide
print(prix)
L'idée du tri par sélection
À chaque passage, on fait trois choses :
- On cherche le plus petit dans la partie qui n'est pas encore triée.
- On l'échange avec la première case de cette partie.
- La zone triée grandit d'une case.
On s'arrête quand il ne reste plus qu'une case. Elle est forcément bien placée.
Exemple travaillé : trier 18, 7, 12, 4, 9
| Passage | Zone à chercher | Plus petit | Échange | Liste après |
|---|---|---|---|---|
| 1 | Cases 0 à 4 | 4 (case 3) | Cases 0 et 3 | 4, 7, 12, 18, 9 |
| 2 | Cases 1 à 4 | 7 (case 1) | Aucun, il est bien placé | 4, 7, 12, 18, 9 |
| 3 | Cases 2 à 4 | 9 (case 4) | Cases 2 et 4 | 4, 7, 9, 18, 12 |
| 4 | Cases 3 à 4 | 12 (case 4) | Cases 3 et 4 | 4, 7, 9, 12, 18 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.