|
La complexité temporelle du tri rapide dans le pire des cas est O(n^2) .
Cela se produit lorsque la sélection pivot entraîne systématiquement des partitions très déséquilibrées. Par exemple, si l’élément le plus petit ou le plus grand est choisi à plusieurs reprises comme pivot. Cela conduit à une partition ayant n-1 éléments et l'autre ayant 0 élément. La récursivité devient alors effectivement similaire au tri par sélection ou au tri à bulles.
|
