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é.
- Ω(n log n)
- Θ(n log n)
- O(n²)
- O(log n)
- non
- oui
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
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.