Projets

[MP02b] Le Tri marrant

Objectifs :

  • Trier un tableau par sélection
  • Découvrir plusieurs autres algorithmes de tri
  • S'interroger sur l'efficacité d'un algorithme

Critères d'évaluation :

  • Compréhension d'un algorithme et la capacité à le mettre en œuvre

Lectures et travail demandés :

I. Premier challenge : "Jeu du Tri Marrant"

  • 2 équipes de 8 élèves maximum

L’élève « chef d’orchestre » se place devant ses camarades  alignés et tenant dans leurs mains une pancarte numérotée.

Objectif du jeu :

  • Le chef d’orchestre doit trier sa ligne, du plus petit numéro au plus grand, et selon une logique unique.
  • Pour chaque défi, l’équipe gagnante est celle qui trie sa ligne le plus rapidement.

Règles du jeu :

Interdiction de parler pour l’équipe, seul le chef d’orchestre 
peut communiquer des ordres avec ses mains

Le chef d’orchestre dispose de 2 ordres :

« Avancer » : sortir un camarade de la ligne et ainsi libérer sa position.
Un seul camarade peut être sorti de la ligne.
« Permuter » : replacer le camarade «sorti»  à la place d’un autre camarade.
Ce dernier doit alors se replacer sur une position vacante de la ligne.

2 épreuves :

  • Figure " libre " : le groupe imagine un algorithme de tri qui sera dirigé par son chef d’orchestre. L’algorithme sera retranscrit en pseudo-code sur le formulaire n°1.

  • Figure " imposée " : le groupe étudie un algorithme de tri imposé par le professeur qui sera dirigé par son chef d’orchestre. L’algorithme sera testé par le groupe en complétant le formulaire n°2.

II. Deuxième challenge : "Codage d'un tri"

[P] On vous propose ici de coder avec processing, le tri proposé par la figure imposée du jeu "Tri marrant".

III. Troisième challenge : "L'efficacité d'un algorithme"

[P] À l'aide de l'animation suivante, essayer de classer l'efficacité des algorithmes présentés par leur rapidité dans deux contextes particuliers :

  • un petit échantillon de données à trier
  • un très grand échantillon de données à trier

Ressources :

[+] Wikipédia : Algorithme de tri
[+] Interstices : Une introduction à la notion de complexité algorithmique