Tri par insertion
Tri par insertion est une expérience interactive de Algorithmes en action, une simulation gratuite de StudyFi Lab qui fonctionne directement dans le navigateur.
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é ?
Questions fréquentes
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.
Comment essayer « Tri par insertion » ?
Lance-le sur un tableau presque trié, puis sur un tableau inversé. Combien de fois plus de décalages faut-il pour l’inversé ?
Tu révises pour un contrôle ?
Importe tes notes et StudyFi les transforme en fiches, tests et podcasts.