Trier : la méthode du joueur de cartes
Objectif : deux tris qu'on peut exécuter à la main
L’essentiel
Ramasser une main de cartes et la ranger est un algorithme de tri, exécuté sans y penser. L'écrire oblige à répondre à des questions qu'on n'avait jamais posées : quel geste exactement, sur quelle carte, et quand s'arrête-t-on ? Deux méthodes se déroulent parfaitement à la main, avec un vrai jeu de cartes sur une vraie table.
À retenir
- Le tri par sélection cherche le plus petit du reste et le met à sa place définitive
- Le tri par insertion glisse chaque nouvel élément à sa place parmi les précédents
- La sélection fait le même travail sur une liste déjà triée, l'insertion en profite
- Un tri est correct si la liste est ordonnée ET contient les mêmes éléments qu'au départ
Le tableau à connaître
| Le tri | Le geste répété | Ce qui est trié en cours de route | L'image |
|---|---|---|---|
| Par SÉLECTION | Chercher le plus petit du reste, le mettre à sa place | Le début de la liste, définitivement | On pioche dans le tas |
| Par INSERTION | Prendre la carte suivante, la glisser au bon endroit | Le début de la liste, provisoirement | On range sa main au fur et à mesure |
⚠ Attention, piège
- Un tri par sélection fait toujours le même nombre de comparaisons, même sur une liste DÉJÀ TRIÉE : il ne le sait pas et vérifie quand même. Le tri par insertion, lui, s'en aperçoit et devient très rapide sur une liste presque triée.
Exemples
- Liste de départ : 5, 3, 8, 1, 9. Passe 1 — on cherche le plus petit parmi les cinq, c'est 1, on l'échange avec la première case.
Le plan de la leçon
- Ce qu'on fait sans y penser
- Sélection ou insertion
- Le tri par sélection, déroulé en entier
- Ce qui rend un tri correct
Je me teste
Après une passe de tri par sélection sur 5, 3, 8, 1, 9, que vaut la liste ?
- 3, 5, 8, 1, 9
- 1, 3, 8, 5, 9
- 1, 3, 5, 8, 9
Quel tri profite d'une liste déjà presque triée ?
- Le tri par insertion
- Le tri par sélection
- Aucun des deux tris
Le mot d’Oscar — Rangez ces cinq cartes, et dites-moi ce que vous faites.
Réponses : 1. B · 2. A