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