Redigerer Kvikksortering (avsnitt)

==== Analyse av gjennomsnittlig tilfelle ====
For å sortere en liste på ''n'' distinkte elementer, krever quicksort en forventet tid på {{mono|'''{{math|''O''(''n'' log ''n'')}}'''}}, i gjennomanitt på alle {{mono|'''{{math|''n''!}}'''}} [[permutasjon]]er av ''n'' elementer [[diskret uniform distribusjon|lik sannsynlighet]]. Vi oppgir her tre vanlige bevis på at denne påstanden gir oss forskjellig innsikt i quicksort's virkemåte.

===== Bruk av persentiler =====
Hvis hver «dreiepinne» har en rangering i de midterste 50%, det vil si mellom den 25. [[persentil]] og den 75. persentil, da sålitter den elementer med minimum 25% og maksimum 75% på hver side. Dersom vi konsekvent kunne velge slike «dreiepinner», da ville vi bare måtte splitte listen maksimum  {{mono|'''<math>\log_{4/3} n</Math>'''}} ganger før vi fikk lister av størrelse 1, noe som ville medføre en {{mono|'''{{math|''O''(''n'' log ''n'')}}'''}}-algoritme.

Når innmatningen er et tilfeldig antall permutasjoner, har «dreiepinnen» en tilfeldig rangering, og det er ikke garantert at den er i de midterste 50%. Når vi likevel starter fra en tilfeldig permutasjon, har «dreiepinnen» i hvert rekursive kall en tilfeldig rangering i sin liste, og vil således være blant de midterste 50 % omkring halvparten av tiden. Dette er godt nok. Forestill deg at du kaster en mynt: [[Mynt]] betyr at «dreiepinnens» rangering er i midten av 50%, krone betyr at den ikke er det. Du kaster mynten igjen og igjen inntil du får ''k'' hoder. Selv om dette ville ta lang tid, er i gjennomsnitt bare {{math|2''k''}} kast påkrevet, og sjansen for at du ikke vil få ''k'' hoder etter ''k'' kast er høyst usannsynlig. Dette kan bli gjort enda mer rigoriøst ved å benytte [[Chernoffavgrensninger]]. Ut fra samme argument vil Quicksort's  rekursjon opphøre etter i gjennomsnitt en kalldybde på bare {{mono|'''<math>2 \log_{4/3} n</math>'''}}. Men hvis gjennomsnittlig kalldybde er {{mono|'''{{math|''O''(log ''n'')}}'''}}, og hvert nivå av kalltreet prosesserer på det meste ''n'' elementer, da vil den totale mengden med arbeid i gjennomsnitt være {{mono|'''{{math|''O''(''n'' log ''n'')}}'''}}. Algoritmen behøver ikke å verifisere at «dreiepinnen» er i den midterste halvdel. Hvis vi møter en konstant på en brøkdel av tiden, vil det være nok for den ønskede kompleksitet.

===== Bruk av recurrency =====
{{seksjonstubb}}