Intentions pédagogiques
De façon générale, les activités de tri ont pour objectif d'appréhender la résolution du problème de tri de données grâce à un algorithme afin de permettre ensuite de comprendre comment les ordinateurs trient des nombres aléatoires dans un certain ordre.
Les élèves sont amenés à exprimer leur point de vue sur l'efficacité, la simplicité et la rapidité des différentes méthodes de tri, de manière à leur suggérer que tous les algorithmes de tri, même s'ils résolvent le même problème (trier), ne se valent pas en terme de complexité, de rapidité et de stockage des données.
Dans cette activité, les élèves doivent suivre un algorithme de tri pas à pas. Cette activité nécessite une argumentation lors des comparaisons et une coopération entre les élèves.
Il s'agit seulement d'exécuter l'algorithme sans chercher à le décrire en détails. Néanmoins, il est intéressant qu'il y ait un temps où l'enseignant fait évoluer l'algorithme au tableau avec l'ensemble les élèves.
Déroulé de l'activité
Faire mettre les participants en file indienne avec une feuille sur laquelle est dessinée une grandeur.
La personne en tête de la file est le Saumon.
Le Saumon avance d'un pas et toute la file aussi puis se met en face de la personne qui était derrière elle.
Le Saumon compare sa valeur avec celle de cette personne et échange les feuilles si elle n'avait pas déjà la plus petite (ou la plus grande) des deux, puis elle avance encore d'un pas et compare/échange si besoin avec la personne suivante.
Une fois au bout de la file, le Saumon s'arrête et attend en cachant sa feuille.
Le Saumon est maintenant la personne en tête de la file, et fait la même chose que la personne précédente, et ainsi de suite jusqu'à ce que tout le monde soit passé., sans prendre en compte le saumon précédent.
Les valeurs sont triées dans l'ordre.
Expérimentation dans le groupe.
Jouez ensemble !
Remédiation
Après l’expérimentation, il est possible de réfléchir au fonctionnement de ce principe.
Il s'agit d'une activité de tri : « le tri systolique »
Les comparaisons sont faites une à une, cette méthode est efficace mais peut s'avérer longue s'il y a un grand nombre d'étiquettes à trier.
Il est alors possible de retrouver avec les élèves l'algorithme permettant de faire ce tri :
Complément :
• Justification du tri : on prouve facilement que la première personne de la file va avoir la plus grande valeur quand elle sera au bout. La deuxième personne aura la 2e valeur la plus grande, et ainsi de suite.
• Complexité : combien de comparaisons fait-on avec cet algorithme ? n personnes (en pratique si on a n personnes la première fait n-1 comparaisons, la deuxième n-2... et la dernière 0). Et si une étape consiste à ce que chacun(e) avance d'un pas, se retourne, puis compare sa valeur avec celle de la personne en face, combien d'étapes cela prend-il ? En pratique le premier se compare avec les n-1 autres (pendant que tout le monde le suit chacun son tour) et quand le premier arrive à la fin le dernier commence à se comparer (avant il attendait l'arrivée du premier) et il va se comparer encore avec n-2 personnes (qui vont lui prendre sa valeur si elle est grande). Une fois que le dernier arrive en tête de file tous les autres ont fini, et personne ne va lui montrer sa valeur, donc plus de comparaisons. Au final on aura n-1 + n-2 étapes, soit environ 2 fois n. Et c'est vraiment *très* rapide, bien plus que les algorithmes de tri habituel, mais rendu possible uniquement parce que chaque porteur de valeur est capable de calculer, et que donc à un moment on a toutes les valeurs qui sont comparées en même temps, deux à deux. En pratique dans un ordinateur classique, même s'il fait du parallélisme, on a un nombre maximum de calculs qu'on peut faire en même temps. Il ne pourra donc pas faire 5000 comparaisons en même temps s'il a 10 000 valeurs, et 500 000 d'un coup s'il a 1000 000 de valeurs. C'est donc un modèle bien particulier qui marche mieux en débranché que dans un ordinateur.
• On peut essayer des variantes de l'algorithme, par exemple prendre la plus petite valeur au lieu de la plus grande valeur,
• D'où vient l'expression « Tri systolique » ? Tout au long des comparaisons, les feuilles circulent le long de la file au fil des comparaisons, un peu comme le flux du sang dans le cœur (systole = contraction des chambres du cœur).
Attention :
Les programmes scolaires demandent de trier, de classer, de ranger des objets ou des collections.
Ce vocabulaire est utilisé notamment en mathématiques ainsi que dans la découverte du vivant pour la détermination ou la classification des espèces.
• Ranger : On ordonne des objets selon leur grandeur dans un ordre croissant ou décroissant
• Classer : On regroupe des objets suivant une caractéristique commune.
• Trier : Comparer chaque objet à une norme fixée, celui qui la possède est conservé, celui qui ne la possède pas est écarté.