Tri rapide

Choisit une valeur, le pivot, puis place les valeurs plus petites à sa gauche et les plus grandes à sa droite. Il recommence ensuite de chaque côté.

meilleur cas Ω(n log n)
cas moyen Θ(n log n)
pire cas O(n²)
espace O(log n)
non stable
en place

Que veulent dire ces termes ?

Meilleur cas : comment le temps grandit avec la taille n de la liste quand l'entrée est la plus facile pour cet algorithme.
Cas moyen : le temps habituel selon n. En n², deux fois plus de valeurs prennent quatre fois plus de temps ; n log n croît bien moins vite.
Pire cas : la croissance sur l'entrée la plus difficile. Utile quand la vitesse ne doit jamais chuter.
Espace : la mémoire supplémentaire nécessaire en plus de la liste. 1 veut dire quelques variables, n une copie de la liste.
Stable : deux valeurs égales gardent leur ordre d'origine. Important quand on trie des fiches selon un seul champ.
En place : trie à l'intérieur de la liste elle-même, sans deuxième liste.

comparaison
déplacement
pivot
à sa place finale

0 / 187 étapes

Comparaisons Échanges

Lancez la lecture : les lignes montrent comment le coût grandit

Vitesse 8 étapes / s

Espace : lecture ou pause. Flèches gauche et droite : pas à pas. Origine et Fin : sauter.

Essayez : Choisissez une liste inversée. Le pivot est toujours le minimum ou le maximum restant, donc un côté reste vide et le coût grimpe vers n².

Comment ça marche

Ici, le pivot est la dernière valeur de la plage. De gauche à droite, chaque valeur qui n'est pas plus grande que le pivot passe du côté gauche par un échange. Puis le pivot se place entre les deux groupes, et il n'en bouge plus. Chaque côté est ensuite trié de la même façon.

Quand le choisir

L'une des façons de trier les plus rapides en pratique, et il n'a presque pas besoin de mémoire en plus. Mais s'il choisit sans cesse un mauvais pivot, par exemple sur une liste déjà triée, il devient lent. Les vraies versions choisissent le pivot avec plus de soin.