Tri rapide

Tri rapide

Quicksort en action sur une liste de nombres aléatoires. Les lignes horizontales sont les valeurs des pivots.

Découvreur ou inventeur	Charles Antony Richard Hoare[1]
Date de découverte	1961[1]
Problèmes liés	Tri par comparaison, diviser pour régner, algorithme de tri
Structure des données	liste ou tableau

Complexité en temps

Pire cas	${\displaystyle O(n^{2})}$[2]
Moyenne	${\displaystyle O(n\log n)}$[2]
Meilleur cas	${\displaystyle O(n\log n)}$[2]

Complexité en espace

Pire cas	${\displaystyle O(n)}$
Moyenne	${\displaystyle O(\log n)}$

modifier - modifier le code - modifier Wikidata

En informatique, le tri rapide ou tri pivot (en anglais quicksort) est un algorithme de tri inventé par C.A.R. Hoare en 1961^[3] et fondé sur la méthode de conception diviser pour régner. C'est un cas particulier de tri par file de priorité en considérant la structure d'arbre binaire de recherche comme file de priorité^[4]. Il est généralement utilisé sur des tableaux, mais peut aussi être adapté aux listes. Dans le cas des tableaux, c'est un tri en place mais non stable.

La complexité moyenne du tri rapide pour n éléments est proportionnelle à n log n, ce qui est optimal pour un tri par comparaison, mais la complexité dans le pire des cas est quadratique. Malgré ce désavantage théorique, c'est en pratique un des tris les plus rapides, et donc un des plus utilisés. Le pire des cas est en effet peu probable lorsque l'algorithme est correctement mis en œuvre et il est possible de s'en prémunir définitivement avec la variante Introsort.

Le tri rapide ne peut cependant pas tirer avantage du fait que l'entrée est déjà presque triée. Dans ce cas particulier, il est plus avantageux d'utiliser le tri par insertion ou l'algorithme smoothsort.