Objectifs

Cette activité illustre la partie exécution d'un algorithme. Le tri à bulles, permettant de trier une suite de nombres, à la manière de bulles remontant à la surface de l'eau, sera présenté aux élèves. Ils pourront ensuite exécuter l'algorithme, comme le ferait une machine, et constater que l'on obtient le résultat voulu dans tous les cas, c'est à dire que la suite de nombres est triée.

Mise en place

L'activité se déroule en classe, avec comme supports un plateau de jeu et des jetons numérotés.

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...

Qu'est-ce que le tri à bulles?

Dans cet exercice, l'algorithme utilisé est le tri à bulles. Imaginez que les nombres à trier sont au fond d'une marre les uns au dessus des autres dans des sortes de bulles (voir dessin: représentation du tri à bulles). On part du haut et on va vers le bas. On compare deux à deux les bulles successives et en fait remonter la bulle la plus légère (avec le plus petit nombre). Quand on est arrivé au fond de la marre, on recommence en haut. Après plusieurs passages, on constate qu'on ne modifie plus l'ordre des bulles sur tout le parcours du haut vers le bas. C'est que les nombres sont triés.

Cet algorithme de tri est appelé le tri à bulles car, petit à petit, les nombres "remontent" vers le début de la liste de nombres, selon leur valeur, à la manière de bulles. Quand le nombre est à sa place, il cesse de "remonter".

Objectifs

L'activité proposée ici permet, avec un matériel simple, d'exécuter l'algorithme de tri à bulles (l'algorithme est donné) et de constater qu'en appliquant rigoureusement une suite d'instructions, on obtient le résultat attendu, même si celui qui exécute ne connait pas l'objectif final. On peut donc séparer la phase de réflexion, de conception, de la phase d'exécution. Et comme cette dernière consiste à suivre des ordres précis, un ordinateur peut la réaliser.

Explications

Le principe du tri à bulles est simple: comparer paire par paire les bulles alignées et faire remonter les plus petites (avec le plus petit nombre). Faire remonter une bulle est simple: lorsque l'on compare une paire de deux bulles, si la bulle la plus petite est plus basse, elle est à remonter, et donc, on la fait passer au dessus de l'autre bulle. On fait ceci en descendant dans la marre, paire par paire, jusqu'à atteindre le fond. A ce moment là, il faut remonter à la surface et recommencer à intervertir l'ordre des bulles qui ne sont pas dans le bon ordre. On s'arrête quand on a fait un trajet partant de la surface, jusqu'au fond, sans avoir changé l'ordre des bulles. Ceci veut dire qu'aucune bulle n'était pas à sa place et que donc, les bulles sont triées de la plus petite à la plus grande, du haut vers le bas. (l'algorithme est présent dans la fiche)

Remarque

Il faut savoir qu'il existe des algorithmes plus efficaces (voir le concept de complexité algorithmique) que le tri à bulles, 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 à bulles (version pdf)
  • Plateau de jeu (version pdf)