Le tri rapide

Le tri rapide - aussi appelé "tri de Hoare" (du nom de son inventeur) ou "tri par segmentation" ou "tri des bijoutiers" ou, en anglais "quicksort" - est certainement l’algorithme de tri interne le plus efficace. Le principe de ce tri est d’ordonner le vecteur T.(0)..T.(n) en cherchant dans celui-ci une clé pivot autour de laquelle réorganiser ses éléments. Il est souhaitable que le pivot soit aussi proche que possible de la clé relative à l’enregistrement central du vecteur, afin qu’il y ait à peu près autant d’éléments le précédant que le suivant, soit environ la moitié des éléments du tableau. On permute ceux-ci de façon à ce que pour un indice j particulier tous les éléments dont la clé est inférieure à pivot se trouvent dans T.(0)...T.(j) et tous ceux dont la clé est supérieure se trouvent dans T.(j+1)...T.(n). On applique ensuite le tri récursivement à T.(1)..T.(1) et T.(j+1)..T(n) afin de trier ces deux segments de tableau. Comme tous les éléments du premier segment ont une clé inférieure ou égale à ceux du second, le tableau sera ainsi entièrement trié.

Dans le tri rapide, le choix du pivot est essentiel. Dans l’implémentation ci-dessus, on se contente de prendre l’élément situé au milieu de la partie à diviser. Mais d’autres stratégies sont possibles.

La complexité dans le pire des cas du tri rapide est en O(n2).