Le tri rapide ou tri Hoare

Algorithmique > Algorithmes de tri > Tri rapide [ Commenter ]

Principe et optimisation

Le tri rapide (ou tri de Hoare) est sans aucun doute le plus utilisé des algorithmes de tri. Le « quicksort » repose sur la devise « divide and conquer » (diviser pour régner).

Comme de nombreux algorithmes de ce type, l'idée générale est de séparer le problème (le tri) en plusieurs sous-problèmes plus simples (le tri de tableaux plus petits). Il s'agit donc un algorithme récursif.

Complexité en temps

Le tri rapide a une complexité en temps de la forme Ω(n.log(n)) dans la plupart des cas. Il fait donc partie, de part ses performances, des concurrents directs du tri par tas et du tri fusion.
Cependant, sa complexité, dans le pire des cas, est quadratique : Ω(n²) ; ce qui est très en deçà de celle du tri par tas.

Conditions et évolutions

Tout comme le tri par tas, le tri rapide est facilement adaptable à différentes situations.

• Pour trier autre chose que des entiers, il suffit de modifier la déclaration de TMyType.
• Pour changer la fonction de compaison, il faut adapter la fonction Compare().
  Celle-ci renvoie "TRUE" si un élément de valeur aV doit être placé avant l'élément de valeur aW dans le tableau trié.

Il ne permet cependant pas directement d'effectuer un tri en temps réel à l'insertion.

Codes sources complets

• Implémentation simple du tri rapide (Code source en Pascal publié le 2006-10-29)
  C'est le premier élément du tableau ou sous-tableau à trier que l'on choisit comme pivot.