La fermeture éclair
Deux élèves ont chacun une pile de copies, déjà rangées de la plus petite note à la plus grande. Tu dois faire une seule pile rangée.
C'est facile : tu regardes la copie du dessus de chaque pile. Tu prends la plus petite. Tu recommences. Les deux piles s'emboîtent comme une fermeture éclair.
Cette ruse est la clé d'un des meilleurs tris : le tri fusion.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Liste triée | Une liste rangée du plus petit au plus grand. | [2, 5, 9] |
| Fusionner | Faire une seule liste triée avec deux listes déjà triées. | [2, 5, 9] et [3, 4, 10] |
| Tri fusion | Un tri qui coupe la liste en deux, trie chaque moitié, puis fusionne. | Couper, trier, fusionner |
| Indice | Le numéro d'une case dans une liste. On compte à partir de 0. | a[0] est le premier nombre de a |
| Comparaison | Regarder deux nombres pour savoir lequel est le plus petit. | 2 est plus petit que 3 |
| Recopier | Ajouter à la fin tout ce qui reste d'une liste, sans rien comparer. | Recopier 10 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : quelle copie en premier ?
À toi de jouer
À toi : quelle copie en premier ?
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
La règle de la fusion
On garde un indice par liste. On compare les deux nombres en tête. On prend le plus petit, et on avance l'indice de sa liste.
Quand une liste est finie, on recopie le reste de l'autre : il est déjà trié.
Exemple travaillé : fusionner deux listes
| Étape | En tête de A | En tête de B | On prend | Résultat |
|---|---|---|---|---|
| 1 | 2 | 3 | 2 | 2 |
| 2 | 5 | 3 | 3 | 2, 3 |
| 3 | 5 | 4 | 4 | 2, 3, 4 |
| 4 | 5 | 10 | 5 | 2, 3, 4, 5 |
| 5 | 9 | 10 | 9 | 2, 3, 4, 5, 9 |
| 6 | A est finie | 10 | 10 (on recopie) | 2, 3, 4, 5, 9, 10 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : fusionner [1, 6] et [2, 3]
À toi de jouer
À toi : fusionner [1, 6] et [2, 3]
4 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.