|
La complexité temporelle du tri rapide, exprimée en notation Big O, varie en fonction des données d'entrée :
* Meilleur cas : O (n journal n)
* Cas moyen : O (n journal n)
* Dans le pire des cas : O(n^2)
Voici une répartition :
* Meilleur cas et cas moyen (O(n log n)) : Cela se produit lorsque l'élément pivot choisi à chaque étape divise le tableau en moitiés à peu près égales. Dans ce scénario, l'algorithme effectue des appels récursifs log n (car il réduit effectivement de moitié la taille du problème), et chaque niveau de récursion nécessite un travail O(n) pour partitionner le tableau. Par conséquent, la complexité temporelle globale est O(n log n).
* Pire des cas (O(n^2)) : Cela se produit lorsque l'élément pivot est à plusieurs reprises l'élément le plus petit ou le plus grand du tableau. Cela conduit à des partitions très inégales. Essentiellement, au lieu de diviser le tableau en deux, vous ne réduisez la taille du problème que d'un élément à chaque fois. Cela se traduit par n appels récursifs, et chaque appel prend toujours un temps de partitionnement de O(n) (car vous comparez presque tous les éléments). Par conséquent, la complexité temporelle globale se dégrade à O(n^2).
Atténuation du pire scénario :
Le pire des cas peut être atténué par :
* Sélection pivot aléatoire : Choisir le pivot au hasard permet d'éviter de choisir systématiquement l'élément le plus petit ou le plus grand, ce qui rend le cas O(n^2) beaucoup moins probable.
* Sélection médiane sur trois pivots : La sélection de la médiane du premier, du milieu et du dernier élément du tableau comme pivot peut également aider à éviter des choix de pivot systématiquement mauvais.
En pratique, Quicksort est souvent très efficace en raison de ses bonnes performances dans les cas moyens et du fait qu'il a tendance à avoir des facteurs constants inférieurs à ceux des autres algorithmes de tri O(n log n) comme Merge Sort. Cependant, il est important d'être conscient du risque de comportement dans le pire des cas O(n^2).
|
