Objectifs

Cette activité illustre la partie exécution d'un algorithme. Les élèves vont pouvoir appliquer l'algorithme de tri appelé le tri par insertion sur une suite de nombres non triée. Ils vont pouvoir constater qu'en exécutant l'algorithme avec rigueur, comme une machine, ils arriveront toujours à leur résultat, c'est à dire trier la suite de nombres.

Mise en place

L'activité se déroule en classe, avec cinq bouteilles (le nombre de bouteilles peut varier, le principe reste toujours le même) et une balance à plateaux.

Introduction

Cet exercice vise à mettre en pratique l'exécution d'un algorithme, qui a été cité dans l'introduction sur l'algorithmique. Nous allons utiliser un exemple typique d'algorithme, l'algorithme de tri. Le tri est présent partout dans un ordinateur. Si vous voulez avoir vos fichiers dans l'ordre alphabétique, l'ordinateur doit lancer une méthode de tri, si vous voulez réorganiser vos photos par date, l'ordinateur va, encore une fois, lancer une procédure de tri, etc...

L'objectif de cette activité est le même que celui du tri à bulles. On donne un algorithme aux élèves et ils l'exécutent. On les amène à prendre conscience qu'on peut séparer l'étape de réflexion, de conception et d'exécution.

Explications

Voici l'intuition du tri par insertion: On a un ensemble d'objets à trier. Pour faire simple, prenons des nombres que l'on veut trier du plus petit au plus grand. On va définir deux listes. L'une avec les objets non triés et l'autre avec les objets triés. Au départ, tous les objets sont dans la liste non triée. On prend le premier objet et on le place dans l'autre liste. Est-ce correct? La liste non triée est toujours non triée, elle a juste un élément en moins. L'autre liste est triée car elle ne contient qu'un seul élément. On peut en effet dire qu'il est plus grand que le précédent (qui n'existe pas) et plus petit que le suivant (qui n'existe pas non plus). Continuons, on prend le premier élément de la liste non triée. On va le mettre dans la liste triée mais cette fois, on ne peut plus le mettre n'importe tout, il faut l'insérer à la bonne place pour préserver l'ordre. On le compare donc avec l'élément qui s'y trouve déjà. S'il est plus petit, on le met au début, s'il est plus grand, on le met à la fin. On a donc toujours bien une liste non triée et une liste triée qui possède maintenant deux éléments. Continuons. On prend le premier élément de la liste non triée. On doit le placer à la bonne place dans la liste triée pour préserver l'ordre. On le compare à chacun des éléments (le premier, puis le deuxième, ...) et s'il est plus petit, on l'insère avant, s'il est plus grand, on continue à comparer avec le suivant dans la liste. Si on est arrivé au bout de la liste, on l'insère à la fin de la liste. Vous avez compris, en répétant ces opérations, on arrive à obtenir des listes triées de plus en plus grandes et la liste non triée devient de plus en plus petite. Quand la liste non triée est vide, on a fini.

Déroulement de l'activité

Le matériel proposé permet de mettre en oeuvre cet algorithme avec les élèves. L'algorithme leur est donné, ils doivent l'exécuter avec rigueur. Au début, ils ne connaissent pas l'objectif poursuivi mais malgré cela, ils finissent par atteindre le but caché qui était de trier les nombres de départ.

Dans le cadre de l'exercice, les deux listes de nombres sont représentées par des suites de bouteilles de poids différents. On prend chaque bouteille, et on l'a compare avec une autre bouteille pour savoir où l'insérer... C'est parce qu'il y a ce mécanisme d'insertion d'une bouteille de la liste non-triée dans une liste triée qu'on appelle cet algorithme le tri par insertion. L'algorithme précis est décrit dans la fiche de l'activité.

Remarque

Il faut savoir que, sauf dans certaines situations particulières, il existe des algorithmes plus efficaces (voir le concept de complexité algorithmique) que le tri par insertion, mais ce dernier à l'avantage d'être facile pour expliquer ce qu'est un algorithme de tri, et d'en donner un exemple.

• Fiche pédagogique (pdf, docx)
• Synthèse pour les élèves (pdf, docx)
• Matériel:
  • Représentation du tri par insertion (pdf, odg)