|
Voici la répartition de la complexité temporelle de Quicksort en notation Big O :
* Meilleur cas : O (n journal n)
* Cela se produit lorsque le pivot choisi à chaque étape divise le tableau en moitiés à peu près égales. Cela conduit à un arbre de récursivité équilibré.
* Cas moyen : O (n journal n)
* En moyenne, Quicksort fonctionne très bien. Il n’est pas nécessaire que la sélection du pivot soit parfaite pour obtenir des performances quasi optimales.
* Dans le pire des cas : O(n^2)
* Cela se produit lorsque le pivot est systématiquement l'élément le plus petit ou le plus grand du tableau. Cela conduit à un arbre de récursion très déséquilibré où un sous-problème a une taille 0 et l’autre une taille n-1. Essentiellement, cela se dégrade et donne des performances similaires au tri par sélection ou au tri à bulles. Un scénario courant est celui où le tableau d’entrée est déjà trié ou presque trié.
Remarques importantes
* Tri rapide aléatoire : Une variante du tri rapide qui sélectionne aléatoirement le pivot réduit considérablement la probabilité de rencontrer le pire des cas. Le tri rapide randomisé a une complexité temporelle moyenne et attendue de O (n log n).
* Tri sur place : Quicksort est un algorithme de tri sur place (il nécessite un minimum de mémoire supplémentaire, généralement O(log n) pour la pile de récursion).
* Performances pratiques : Malgré la possibilité du pire des cas O(n^2), le tri rapide est souvent très efficace en pratique et est fréquemment utilisé dans les fonctions de tri standard des bibliothèques. Ses avantages incluent sa nature sur place et ses facteurs constants relativement faibles.
* Comparaison avec le tri par fusion : Le tri par fusion a une complexité temporelle O(n log n) garantie dans tous les cas, mais il n'est pas sur place (nécessite un espace auxiliaire O(n)). Par conséquent, le tri rapide est souvent préféré lorsque l’espace est un problème majeur et que les données doivent être raisonnablement bien réparties.
En résumé :
| Cas | Complexité temporelle |
|-------------|-----------------|
| Meilleur | O(n journal n) |
| Moyenne | O(n journal n) |
| Le pire | O(n^2) |
|
