Tri fusion
Tri fusion est une expérience interactive de Algorithmes en action, une simulation gratuite de StudyFi Lab qui fonctionne directement dans le navigateur.
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.
Questions fréquentes
Que montre l’expérience « 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.
Comment essayer « Tri fusion » ?
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.
Tu révises pour un contrôle ?
Importe tes notes et StudyFi les transforme en fiches, tests et podcasts.