Time and Space Complexity

Complexité temporelle :

• Cas moyen : O(n log n)
  • Un pivot équilibré divise le tableau approximativement en deux à chaque fois, ce qui donne environ log n niveaux de travail de partitionnement en O(n).
• Pire cas : O(n²)
  • Si le pivot est toujours le plus petit ou le plus grand élément (par exemple, un tableau déjà trié avec le dernier élément comme pivot), un côté est vide à chaque fois et la récursion atteint n niveaux de profondeur.

Complexité spatiale :

• O(n) pour la version que nous construisons ici, car nous créons de nouvelles listes plus petites et plus grandes à chaque étape. Le Quick Sort classique in-place (sur place) améliore cela à un espace supplémentaire de O(log n).

Résumé :

• Le Quick Sort est très rapide en moyenne et constitue un algorithme de tri de référence en pratique.
• Un mauvais choix de pivot peut le dégrader en O(n²) ; de bonnes stratégies de pivot (comme choisir un élément aléatoire ou la médiane) évitent cela.