Motivation

Le tri rapide (Quick Sort) fonctionne en choisissant un pivot et en partitionnant le tableau autour de celui-ci : les valeurs plus petites vont d'un côté, les valeurs plus grandes de l'autre. Chaque côté est ensuite trié de la même manière.

Pourquoi apprendre le Quick Sort ?

• Rapide en pratique : en moyenne, il s'exécute en un temps O(n log n) et est souvent plus rapide que d'autres tris en O(n log n).
• Largement utilisé : de nombreuses fonctions de tri des bibliothèques standard sont basées sur le Quick Sort ou l'une de ses variantes.
• Diviser pour régner : il renforce un modèle utilisé dans de nombreux algorithmes avancés.
• Le choix du pivot est crucial : il montre comment un seul choix de conception (le pivot) affecte les performances, passant de O(n log n) à O(n²).