Algorithmes de tri

Cette simulation rend le tri visible. Chaque barre représente un nombre, et l'algorithme choisi compare les barres et les échange jusqu'à ce qu'elles soient rangées dans l'ordre. Les élèves choisissent parmi cinq algorithmes, règlent le nombre de barres et le nombre d'étapes par seconde, et peuvent mélanger pour recommencer. Les affichages comptent les comparaisons, les échanges ou écritures, et indiquent l'état. Faire tourner deux algorithmes sur le même nombre de barres montre pourquoi certains sont bien plus rapides sur les grandes listes, ce qui en fait un bon point de départ pour les cours d'informatique sur l'efficacité.

• Choisissez Bulle, appuyez sur Mélanger, et notez les compteurs Comparaisons et Échanges / écritures à la fin.
• Recommencez avec Rapide ou Fusion au même nombre de Barres et comparez les compteurs.
• Réglez les Barres sur 80 et observez combien de temps les algorithmes plus lents mettent à finir.
• Réduisez les Étapes/s et repérez quelles barres sont en cours de comparaison et lesquelles viennent d'être échangées.
• Comparez Insertion et Sélection sur la même rangée mélangée.

1. 1Décrivez le fonctionnement des tris à bulles, par insertion, par sélection, rapide et fusion.
2. 2Comparez les algorithmes en comptant les comparaisons et les échanges.
3. 3Expliquez pourquoi les tris rapide et fusion passent mieux à l'échelle que les tris plus simples.
4. 4Prévoyez comment le travail augmente lorsque la liste s'allonge.

Questions fréquentes des enseignants