Här är uppdelningen av Quicksorts tidskomplexitet i Big O Notation:
* bästa fall: O (n log n)
* Detta inträffar när den sväng som valts vid varje steg delar upp matrisen i ungefär lika stora halvor. Detta leder till ett balanserat rekursionsträd.
* Genomsnittligt fall: O (n log n)
* I genomsnitt presterar QuickSort mycket bra. Valet av pivot behöver inte vara perfekt för att uppnå nästan optimal prestanda.
* värsta fall: O (n^2)
* Detta händer när pivoten är konsekvent det minsta eller största elementet i matrisen. Detta leder till ett mycket obalanserat rekursionsträd där ett underproblem har storlek 0 och det andra har storlek N-1. I huvudsak försämras det till prestanda som liknar sorteringssortering eller bubbelsorter. Ett vanligt scenario är när ingångsgruppen redan är sorterad eller nästan sorterad.
Viktiga anteckningar
* Randomiserad kvicksort: En variation av kvicksort som slumpmässigt väljer pivoten minskar sannolikheten för att möta det värsta fallet. Randomiserad kvicksort har en genomsnittlig och förväntad tidskomplexitet av O (n log n).
* på plats sortering: QuickSort är en sorteringsalgoritm på plats (det kräver minimalt extra minne, vanligtvis O (log N) för rekursionsstacken).
* Praktisk prestanda: Trots möjligheten till en värsta fall O (n^2) är Quicksort ofta mycket effektiv i praktiken och används ofta i standardbibliotekssorteringsfunktioner. Dess fördelar inkluderar dess natur på plats och relativt små konstant faktorer.
* Jämförelse med Merge Sort: Fusion Sort har en garanterad o (n log n) tidskomplexitet i alla fall, men det är inte på plats (kräver o (n) extrautrymme). Därför föredras Quicksort ofta när utrymmet är ett stort problem och uppgifterna förväntas vara rimligt välfördelade.
Sammanfattningsvis:
| Fall | Tidskomplexitet |
| ------------- | ----------------- |
| Bästa | O (n log n) |
| Genomsnitt | O (n log n) |
| Värst | O (n^2) |
