6.3.1.2 : Le tri rapide
La figure 22 illustre le fonctionnement du tri rapide. Dans cet algorithme, on commence par choisir une valeur au hasard qui servira de pivot pour toutes les autres. Les valeurs plus grandes seront déplacées à droite du pivot tandis que les autres seront déplacées à gauche. Ensuite on applique la même règle au sein des deux ensembles de valeurs de chaque côté du pivot jusqu'à ce que toutes les données soient triées.
Sa complexité est $O\left(N \log_2 N\right)$
.
Figure 22 : Illustration du tri rapide.