Tri rapide - Définition

Choix du pivot et complexité

Pivot arbitraire

Une manière simple de choisir le pivot est de prendre toujours le premier élément du sous-tableau courant (ou le dernier). Lorsque toutes les permutations possibles des entrées sont équiprobables, la complexité moyenne du tri rapide en sélectionnant le pivot de cette façon est Θ(n log n). Cependant, la complexité dans le pire cas est Θ(n²), et celle-ci est atteinte lorsque l'entrée est déjà triée ou presque triée.

Si on prend comme pivot le milieu du tableau, le résultat est identique, bien que les entrées problématiques soient différentes.

Il est possible d'appliquer une permutation aléatoire au tableau pour éviter que l'algorithme soit systématiquement lent sur certaines entrées. Cependant, cette technique est généralement moins efficace que de choisir le pivot aléatoirement.

Pivot aléatoire

Si on utilise la méthode donnée dans la description de l'algorithme, c'est-à-dire choisir le pivot aléatoirement de manière uniforme parmi tous les éléments, alors la complexité moyenne du tri rapide est Θ(n log n) sur n'importe quelle entrée. Dans le pire cas, la complexité est Θ(n²). Néanmoins, l'écart type de la complexité est seulement Θ(n), ce qui signifie que l'algorithme s'écarte peu du temps d'exécution moyen.

Dans le meilleur cas, l'algorithme est en Θ(n log n).

Pivot optimal

En théorie, on pourrait faire en sorte que la complexité de l'algorithme soit Θ(n log n) dans le pire cas en prenant comme pivot la valeur médiane du sous-tableau. L'algorithme BFPRT ou médiane des médianes permet en effet de calculer cette médiane de façon déterministe en temps linéaire. Mais l'algorithme n'est pas suffisamment efficace dans la pratique, et cette variante est peu utilisée.