Les cartes dans ta main
Tu joues aux cartes. On te distribue tes cartes une par une. Que fais-tu ?
Tu prends la première. Puis la deuxième : tu la glisses avant ou après la première, selon sa valeur. Puis la troisième, et ainsi de suite.
Tes cartes sont toujours rangées, même avant la fin de la distribution. C'est le tri par insertion.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Insertion | Glisser une valeur à sa place dans une liste déjà triée. | Glisser le 6 entre le 5 et le 8 |
| Partie triée | Le début de la liste, déjà rangé. | 3, 7 après la deuxième carte |
| Décalage | Pousser une valeur d'une case vers la droite pour faire de la place. | Le 7 passe de la case 0 à la case 1 |
| Place | La case où la valeur doit finir. | Le 2 va en case 0 |
| Copie | Une nouvelle liste avec les mêmes valeurs. On peut la changer sans toucher à l'originale. | copie = [] |
| Tri en place | Un tri qui range la liste elle-même, sans en fabriquer une autre. | Le tri par sélection du cours précédent |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : range ta main
À toi de jouer
À toi : range ta main
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
L'idée du tri par insertion
La liste a deux parties. À gauche, la partie triée. Au début, elle ne contient que la première valeur. À droite, ce qui n'est pas encore regardé.
À chaque tour, on prend la première valeur de la droite. On la compare aux valeurs de la partie triée, en partant de la fin. Tant qu'une valeur est plus grande, on la pousse d'une case : c'est un décalage. Puis on pose la valeur dans le trou.
Exemple travaillé : trier 7, 3, 9, 2, 5
| Carte prise | Cartes poussées | Liste après | Décalages |
|---|---|---|---|
| Départ | - | 7, 3, 9, 2, 5 | - |
| 3 | Le 7 | 3, 7, 9, 2, 5 | 1 |
| 9 | Aucune | 3, 7, 9, 2, 5 | 0 |
| 2 | Le 9, le 7, le 3 | 2, 3, 7, 9, 5 | 3 |
| 5 | Le 9, le 7 | 2, 3, 5, 7, 9 | 2 |
| Total | - | Liste triée | 6 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : l'état après l'étape 3
À toi de jouer
À toi : l'état après l'étape 3
4 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.