Tidskompleksiteten af ​​Quicksort, udtrykt i stor O -notation, varierer afhængigt af inputdataene:

* Bedste tilfælde: O (n log n)

* Gennemsnitlig sag: O (n log n)

* værste tilfælde: O (n^2)

Her er en sammenbrud:

* Bedste sag og gennemsnitlig sag (O (n log n)): Dette forekommer, når det drejelede element, der er valgt på hvert trin, deler matrixen i omtrent lige store halvdele. I dette scenarie foretager algoritmen log n rekursive opkald (fordi det effektivt halverer problemstørrelsen), og hvert rekursionsniveau kræver O (n) arbejde for at opdele arrayet. Derfor er den samlede tidskompleksitet O (n log n).

* værste tilfælde (O (n^2)): Dette sker, når drejelementet gentagne gange er det mindste eller største element i matrixen. Dette fører til meget ujævne partitioner. I det væsentlige, i stedet for at opdele matrixen i halvdelen, reducerer du kun problemstørrelsen med et element hver gang. Dette resulterer i n rekursive opkald, og hvert opkald tager stadig O (n) tid til at partitionere (fordi du sammenligner næsten alle elementer). Følgelig forringes den samlede tidskompleksitet til O (n^2).

afbødning af worst-case scenario:

Det værste tilfælde kan mindskes af:

* Randomiseret drejepunkt: Valg af pivot tilfældigt hjælper med at undgå konsekvent at vælge det mindste eller største element, hvilket gør O (N^2) sagen meget mindre sandsynlig.

* Median-of-tre-drejningsvalg: Valg af median af den første, midterste og sidste elementer i matrixen som drejning kan også hjælpe med at undgå konsekvent dårlige drejevalg.

I praksis er QuickSort ofte meget effektiv på grund af dens gode gennemsnitlige case-ydeevne, og det faktum, at det har en tendens til at have lavere konstante faktorer end andre O (n log n) sorteringsalgoritmer som Merge Sort. Det er dog vigtigt at være opmærksom på potentialet for O (N^2) værste tilfælde.