Simulic
Français

Tri visuel : tri à bulles, par sélection, par insertion et par fusion pas à pas

InformatiqueAlgorithmique et résolution de problèmes13–14 ans

Chargement…

Utiliser avec ma classe ✨ Personnaliser avec l'IA Signaler un problème

Une suite de nombres est représentée par des barres ; choisissez le tri à bulles, le tri par sélection, le tri par insertion ou le tri par fusion, puis appuyez sur Pas à pas ou Lancer. Chaque étape met en évidence la paire comparée, la paire échangée et la partie déjà triée, tout en comptant les comparaisons et les échanges ; la ligne de pseudo-code correspondante est aussi surlignée. Le tri par fusion coupe les barres en deux niveau par niveau puis les fusionne, et un tableau et un graphique comparent les comparaisons des quatre algorithmes (n log n face à n²). Les élèves peuvent faire glisser une barre pour changer sa valeur avant de lancer.

Leçon : Algorithmes de tri (à bulles, par sélection, par insertion, par fusion), boucles imbriquées et diviser pour régner

Ce qu’elle montre

Le tri à bulles, le tri par sélection et le tri par insertion utilisent des boucles imbriquées : pour n éléments, ils demandent environ n²/2 comparaisons dans le pire des cas. Le tri par sélection fait au plus n − 1 échanges, le tri à bulles peut s’arrêter plus tôt et le tri par insertion excelle sur une liste presque triée. Le tri par fusion applique « diviser pour régner » : il coupe la liste en deux jusqu’à obtenir des éléments seuls, puis fusionne les moitiés triées. Ses quelque log₂n niveaux coûtent chacun au plus n comparaisons, soit environ n·log₂n au total, bien moins que n²/2 pour n grand.

Mode d’emploi

Commencez avec environ 8 éléments et cliquez sur Pas à pas ; les élèves prédisent chaque comparaison surlignée en suivant la ligne de pseudo-code. Cliquez sur Lancer et notez comparaisons et échanges, puis changez d’Algorithme et recommencez avec les options Décroissante et Presque triée. Choisissez Tri par fusion pour voir les barres se séparer niveau par niveau puis se rejoindre ; le tableau et le graphique en dessous font passer la même suite par les quatre algorithmes. Vous pouvez aussi faire glisser une barre avant de lancer.

Paramètres modifiables

  • Nombre d’éléments 4–30
  • Algorithme Tri à bulles, Tri par sélection, Tri par insertion, Tri par fusion
  • Suite initiale Aléatoire, Décroissante (pire des cas), Presque triée
  • Vitesse d’exécution 1–20 étapes/s
  • Afficher la comparaison des quatre algorithmes

Questions à explorer

  1. Après la première passe du tri à bulles, quel élément est forcément à sa place définitive ?
  2. Quel algorithme fait le moins d’échanges sur une suite décroissante, et pourquoi ?
  3. Pourquoi le tri par insertion se termine-t-il si vite sur une suite presque triée ?

Simulations associées