Illustration

On illustre le principe de tri par insertion à l'aide d'un jeu de cartes à trier, le tas de cartes et la main tenant les cartes étant maintenant représentés par un tableau.

Note

Pas de code python dans cette première page: papier et crayon pour les premiers pas et comprendre le principe.

Rappel: la démarche consistant à commencer par papier-crayon pour faire des tentatives, avant d'écrire la moindre ligne de code, doit toujours être votre démarche lorsqu'on vous demande de réfléchir à un nouvel algorithme.

Un exemple

On veut trier, comme le joueur de cartes, le tableau tas = [4,2,7,1,8,5,3].

• Au départ: main = [] et tas = [4,2,7,1,8,5,3].
• Dans la main, on place la carte du haut (on décide ici que la carte du haut est le début de liste): main = [4], tas = [2,7,1,8,5,3].
• Puis on insère la carte du haut du tas à sa place dans la main: main = [2,4], tas = [7,1,8,5,3].
• On recommence: main = [2,4,7], tas = [1,8,5,3].
• main = [1,2,4,7], tas = [8,5,3].
• main = [1,2,4,7,8], tas = [5,3].
• main = [1,2,4,5,7,8], tas = [3].
• main = [1,2,3,4,5,7,8], tas = [].

Exercice

Illustrer de même le tri du joueur de cartes avec le tas de cartes initial tas = [8, 1, 7, 2, 4, 3, 1, 6].

Réponse

• main = [], tas = [8, 1, 7, 2, 4, 3, 1, 6].
• main = [8], tas = [1, 7, 2, 4, 3, 1, 6].
• main = [1, 8], tas = [7, 2, 4, 3, 1, 6].
• main = [1, 7, 8], tas = [2, 4, 3, 1, 6].
• main = [1, 2, 7, 8], tas = [4, 3, 1, 6].
• main = [1, 2, 4, 7, 8], tas = [3, 1, 6].
• main = [1, 2, 3, 4, 7, 8], tas = [1, 6].
• main = [1, 1, 2, 3, 4, 7, 8], tas = [6].
• main = [1, 1, 2, 3, 4, 6, 7, 8], tas = [].