À retenir
- Fonctionne par récursivité (le programme s'appelle lui-même sur des portions de plus en plus petites).
- Est considéré comme l'un des algorithmes de tri les plus rapides en pratique.
- Effectue le tri directement « sur place », sans nécessiter beaucoup de mémoire vive additionnelle.
Le tri rapide est une méthode très efficace pour organiser une liste d'éléments (comme des nombres ou des mots) dans un ordre précis. Il fonctionne selon le principe « diviser pour régner » : on choisit un élément de référence appelé pivot, puis on place tous les éléments plus petits d'un côté et les plus grands de l'autre, avant de recommencer l'opération sur les deux groupes obtenus.
Étymologie
Traduction directe de l'anglais Quicksort. Cet algorithme a été inventé par l'informaticien britannique Tony Hoare en 1959. Le nom souligne sa rapidité d'exécution par rapport aux méthodes de tri plus rudimentaires de l'époque.
Exemples d'usage
- Organiser une liste de 10 000 noms par ordre alphabétique en quelques millisecondes.
- Classer les scores des joueurs d'un jeu vidéo du plus haut au plus bas.
- Utilisation de la fonction
std::sorten C++ ou certaines implémentations desort()en Java.
Cas d'usage
Il est utilisé massivement dans le développement logiciel dès qu'il s'agit de traiter de grands volumes de données. On le retrouve dans les moteurs de recherche, les bases de données et les bibliothèques standards de nombreux langages de programmation en raison de sa faible consommation de mémoire supplémentaire.
Bonnes pratiques
Pour éviter que l'algorithme ne devienne lent (cas critique), il est recommandé de bien choisir le pivot (par exemple en prenant la valeur centrale de la liste plutôt que la première). Pour de toutes petites listes, il est souvent plus efficace de basculer sur un tri par insertion, plus simple.
Synonymes
Antonymes
Conseil
Si vous débutez, essayez de visualiser l'algorithme avec un jeu de cartes : posez une carte sur la table (le pivot), puis créez un tas à gauche pour les cartes inférieures et un tas à droite pour les supérieures. Répétez l'opération pour chaque tas. C'est la meilleure façon de comprendre la récursivité !
Questions fréquentes
Le tri rapide est-il toujours le meilleur choix ?
Pas forcément. Bien qu'excellent en moyenne, il peut être lent sur des listes déjà presque triées si le pivot est mal choisi.
C'est quoi un pivot ?
C'est un élément arbitraire de la liste qui sert de frontière pour séparer les données en deux groupes : les 'petits' et les 'grands'.