Algorithmes en action
Algorithmes en action est une simulation interactive gratuite de StudyFi Lab. Elle fonctionne directement dans le navigateur, sans inscription ni installation.
Trier et chercher, pas à pas
Expériences
Tri à bulles
Le tri à bulles compare des éléments voisins et les échange s’ils sont dans le mauvais ordre. Après chaque passage, le plus grand élément est « remonté » à la fin, donc la partie non triée raccourcit. Si un passage ne fait aucun échange, le tableau est trié. Dans le pire cas, il faut n(n−1)/2 comparaisons, soit O(n²).
Essaie ceci: Choisis l’entrée inversée et compare le nombre de comparaisons avec n(n−1)/2. Essaie ensuite un tableau presque trié : il s’arrête après quelques passages.
Tri par insertion
Le tri par insertion fonctionne comme ranger des cartes dans sa main : la partie gauche est déjà triée, et chaque nouvel élément (key) glisse vers la gauche jusqu’à rencontrer un plus petit. Les éléments plus grands se décalent d’une case vers la droite. Sur des données aléatoires, c’est O(n²), mais sur des données presque triées presque O(n) : un tableau trié ne demande que n−1 comparaisons.
Essaie ceci: Lance-le sur un tableau presque trié, puis sur un tableau inversé. Combien de fois plus de décalages faut-il pour l’inversé ?
Tri fusion
Le tri fusion coupe le tableau en deux moitiés, trie chacune de la même façon (récursivité), puis fusionne les deux moitiés triées : il prend toujours le plus petit des deux éléments de tête. Couper en deux donne log₂ n niveaux et chaque niveau traite les n éléments, donc le temps est toujours O(n log n). En cas d’égalité, il prend l’élément de gauche : il est donc stable.
Essaie ceci: Essaie un tableau inversé puis un tableau presque trié de même taille. Le nombre de comparaisons change à peine : l’ordre de l’entrée compte peu.
Tri rapide
Le tri rapide choisit un pivot — ici le dernier élément de la plage (partition de Lomuto) — et réorganise la plage pour que les plus petits passent à gauche et les autres à droite. Le pivot se retrouve alors à sa place définitive, et les deux parties sont triées de la même façon. En moyenne c’est O(n log n), mais si le pivot partage mal (par exemple sur un tableau déjà trié ou inversé), on tombe à O(n²).
Essaie ceci: Compare une entrée aléatoire et une entrée inversée. Sur le tableau inversé, le pivot est toujours le plus grand ou le plus petit : regarde les comparaisons s’envoler.
Recherche linéaire vs dichotomique
La recherche linéaire examine les éléments un par un, donc dans le pire cas il faut n étapes : O(n). La recherche dichotomique ne marche que sur un tableau trié : elle regarde au milieu et, selon le résultat, élimine toute une moitié. Après chaque étape il reste au plus la moitié, donc ⌈log₂(n+1)⌉ étapes au plus suffisent : O(log n). Pour 40 éléments, c’est 6 étapes au lieu de 40.
Essaie ceci: Mets 40 éléments et cherche la dernière valeur. Choisis ensuite un nombre absent du tableau : combien d’étapes faut-il à chaque recherche pour s’en rendre compte ?
Course de tris
Les quatre algorithmes trient la même entrée, et dans chaque couloir une étape correspond à une comparaison ou à un déplacement. Les algorithmes en O(n²) (à bulles et par insertion) croissent avec la taille du tableau bien plus vite que ceux en O(n log n) (fusion et rapide). L’ordre dépend aussi de l’entrée : sur un tableau presque trié, le tri par insertion gagne souvent.
Essaie ceci: Lance la course sur un tableau aléatoire de 40 éléments, puis passe à presque trié. Le gagnant change-t-il ?
Questions fréquentes
Qu’est-ce que Algorithmes en action ?
Algorithmes en action est une simulation interactive gratuite de StudyFi Lab. Elle fonctionne directement dans le navigateur, sans inscription ni installation. Trier et chercher, pas à pas
Algorithmes en action est-il gratuit ?
Oui. Algorithmes en action est entièrement gratuit. Il fonctionne dans le navigateur sur ordinateur, tablette et téléphone, sans compte.
Que puis-je explorer dans Algorithmes en action ?
Tri à bulles, Tri par insertion, Tri fusion, Tri rapide, Recherche linéaire vs dichotomique, Course de tris.
Que montre l’expérience « Tri à bulles » ?
Le tri à bulles compare des éléments voisins et les échange s’ils sont dans le mauvais ordre. Après chaque passage, le plus grand élément est « remonté » à la fin, donc la partie non triée raccourcit. Si un passage ne fait aucun échange, le tableau est trié. Dans le pire cas, il faut n(n−1)/2 comparaisons, soit O(n²).
Que montre l’expérience « Tri par insertion » ?
Le tri par insertion fonctionne comme ranger des cartes dans sa main : la partie gauche est déjà triée, et chaque nouvel élément (key) glisse vers la gauche jusqu’à rencontrer un plus petit. Les éléments plus grands se décalent d’une case vers la droite. Sur des données aléatoires, c’est O(n²), mais sur des données presque triées presque O(n) : un tableau trié ne demande que n−1 comparaisons.
Tu révises pour un contrôle ?
Importe tes notes et StudyFi les transforme en fiches, tests et podcasts.