Redigerer Kvikksortering (avsnitt)

===Ulike former for implementasjon===
====Valg av «dreietapp»====
I de aller første tidlige versjonene av quicksort, kunne elementet til venstre av partisjonen ofte bli valgt som «dreietapp». Uheldigvis, forårsaker dette en adferd av det verste tilfelle på tabeller som allerede er sortert, noe som er et vanlig tilfelle. Dette problemet ble lett løst ved å enten velge en tilfeldig indeks for «dreietappen», enten i form av den midterste indeksen i partisjonen eller (særlig for lange partisjoner) medianen av det første, midterste og siste elementet av partisjonen. Denne løsningen ble foreslått av Robert Sedgewick.<ref name="Sedgewick1998"/><ref name="Sedgewick1978"/> Denne «medianen-av-tre» regelen teller tilfeller av sortert (eller det omvendte av sortert) innmatning, og gir et bedre estimat på den optimale «dreietapp» (den sanne median) enn å velge et hvilket som helst enkeltelement når ingen informasjon om rekkefølgen er tilstede.

Det forventede antallet sammenligninger som er nødvendig for å sortere {{math|''n''}} er

:{{mono|'''{{math|''n''}} = {{math|1.386 ''n'' log ''n''}}'''}}.

«Medianen-av-tre» regelen bringer dette ned i 

: {{mono|'''{{math|''C''<sub>''n'', 2</sub> ≈ 1.188 ''n'' log ''n''}}'''}}

(der {{mono|'''C'''}} er [[binomialkoeffisient]]en) på bekostninga av en forventet økning av bytter.<ref name="Bentley1993"/> En mer kraftig regel for valg av «dreietapp», for større tabeller, er å velge ''ninther'', en rekursiv «median-av-tre» (Mo3), definert som:<ref name="Bentley1993"/>

:{{mono|'''{{math|ninther(''a'') {{=}} median (Mo3(første ⅓ av ''a''), Mo3(midterste ⅓ av ''a''), Mo3(siste ⅓ av ''a''))}}'''}}

Valg av «dreietapp» kompliseres også av eksistensen av [[heltallsoverflyt]]. Dersom grenseindeksene for undertabellen som blir sortert er tilstrekkelig store, vil det enkle uttrykk for middelindeksen {{math|(''lo'' + ''hi'')/2}} forårsake overflyt og gi en feilaktig «dreietapp»-indeks. Dette kan bli unngått ved å bruke, for eksempel, {{math|''lo'' + (''hi''−''lo'')/2}} til å indeksere det midterste elementet, på bekostning av en mer kompleks [[aritmetikk]]. Lignende problemstillinger oppstår i en del andre metoder for valg av «dreietapp».

====Repeterte elementer====
For partisjonsalgoritmer slik som de som er beskrevet ovenfor (også de som velger gode «dreietapp»-verdier), fremviser quicksort en dårlig ytelse hvis tabellen inneholder mange repeterende elementer. Problemet er tydelig når alle elementer i tabellen er like: I hver rekursjon er venstre partisjon tom (ingen verdi er mindre enn «dreietappen»), og høyre partisjon har bare minsket med et element («dreietappen» er fjernet). Denne algoritmen krever konsekvent [[tidskompleksitet|kvadratisk tid]] for å sortere en tabell med like verdier.

For å løse dette problemet, som noen ganger blir kalt «[[det nederlandske flaggets problem]]»,<ref name="Bentley1993"/> kan en alternativ partisjonsrutine som bruker lineær tid bli brukt for å dele verdiene opp i tre grupper: Verdier mindre enn «dreietappen», verdier like store som «dreietappen» og verdier større enn «dreietappen». Jon Bentley og Douglas McIlroy har kalt dette en «feit partisjon» og har bemerket at den allerede ble implementert i {{mono|[[qsort]]}} i [[UNIX versjon 7]] (1979).<ref name="Bentley1993"/> Verdiene som er identisk med «dreietappen» er allerede sortert, slik at bare partisjoner som er mindre enn og større enn «dreietappen» krever en rekursiv sortering. I pseudokode blir quicksort-algoritmen slik:

 '''algoritme''' quicksort(A, lo, hi) '''er'''
     '''if''' lo < hi '''then'''
         p := pivot(A, lo, hi)
         left, right := partition(A, p, lo, hi)  ''// Flere returverdier''
         quicksort(A, lo, left)
         quicksort(A, right, hi)

Det beste tilfelle for algortitmen inntreffer nå når alle elementer er identiske, eller blir valgt fra en liten mengde av {{mono|'''{{math|''k'' ≪ ''n''}}'''}} elementer. I tilfeller med bare identiske elementer, vil den modifiserte quicksort utføre på det meste to rekursive kall på tomme undertabeller og således avsluttes i lineær tid.

====Optimaliseringer====
To andre viktige optimaliseringer, ble foreslått av Sedgewick, og er mye utbredt i praksis. Blant annet brukes de av [[GNU C Library]] (glibc). De består i:<ref name="GNUC2017"/>

*For å være sikker på at for det meste {{mono|'''{{math|''O''(log ''n'')}}'''}} minne blir brukt, utfører vi rekursivt den minste siden av partisjonen, og deretter foretar et kall for å utføre rekursjon på den andre.
*Når antall elementer er under en viss grense (kanskje ti elementer), svitsjer vi til en ikke-rekursiv sorteringslagoritme som utfører færre ombyttinger, sammenligninger eller andre operasjoner på såpass små tabeller
*En eldre variant av den tidligere optimalisering: Når antallet elementer er mindre enn terskelen ''k'', stopper vi kort og godt opp; etter at hele tabellen har blitt prosessert, foretar vi innstikksortering på den. Å stoppe rekursjonen tidlig etterlater tabellen ''k''-sortert, som betyr at hvert element er maksimalt ''k'' posisjoner unna sin endelige ferdigsorterte form. I dette tilfellet krever innstikksorteringen en tid på {{mono|'''{{math|''O''(''kn'')}}'''}} for å avslutte sorteringen, en tid som er lineær hvis ''k'' er en konstant.<ref name="Sedgewick1978"/><ref name="Bentley1999_117"/> Sammenlignet med mange «småsorterings»-optimaliseringer, kan denne versjonen utføre færre instruksjoner, men den gjør ikke optimal bruk av [[hurtigminne]]t i moderne datamaskiner.<ref name="LaMarca1999"/>

====Parallellisering====
Quicksorts splitt og hersk-formulering gjør den egnet for [[parallell algoritme|parallellisering]] ved å bruke [[oppgaveparallellisme]]. Partisjoneringstrinnet blir oppnådd gjennom bruken av en [[prefixsum|parallell prefixsum]]-algoritme for å beregne en indeks for hvert tabellelement i sin seksjon av den partisjonerte tabellen.<ref name="Acar2013"/><ref name="Breshears2012"/> Dersom vi har en tabell av størrelse {{mono|'''{{math|''n''}}'''}}, utfører partisjoneringstrinnet et arbeid på {{mono|'''{{math|O(''n'')}}'''}} i tidsrommet {{mono|'''{{math|''O''(log ''n'')}}'''}} som krever {{mono|'''{{math|O(''n'')}}'''}} tilleggsplass. Etter at tabellen har blitt partisjonert, kan de to partisjonene bli sortert rekursivt i parallell. Ved å anta et ideelt valg for «dreiepinner», sorterer parallell quicksort en tabell av størrelse {{mono|'''{{math|''n''}}'''}} med et arbeid på {{mono|'''{{math|O(''n'' log ''n'')}}'''}} i tidsrommet {{mono|'''{{math|O(log² ''n'')}}'''}} ved å bruke {{mono|'''{{math|O(''n'')}}'''}} tilleggsplass.

Quicksort har enkelte ulemper sammenlignet med andre sorteringsalgoritmer, eksempelvis [[flettesortering]], som kompliserer dets effektive parallellisering. Dybden av quicksort's splitt-og-hersk tre påvirker direkte algortimens skalerbarhet, og denne dybden er svært avhengig av algoritmens «dreiepinne». I tillegg er det vanskelig å parallellisere partisjoneringstrinnet på-stedet. Bruken av tilleggs-lagringsplass forenkler partisjoneringstrinnet, men øker algortimens bruk av minne og gir konstante [[overhead (informatikk)|overhead]].

Andre mer sofistikerte parallele sorteringsalgoritmer kan oppnå dette innenfor bedre tidsgrenser.<ref name="Miller2000"/> I 1991 beskrev for eksempel David Powers en parallellisert quicksort (og en beslektet [[radixsortering]]) som kan operere med en tid på {{mono|'''{{math|''O''(log ''n'')}}'''}} på en CRCW [[Parallel random access-machine|PRAM]] (''parallel random-access machine'') med ''n'' [[mikroprosessor]]er som utfører partisjonering implisitt.<ref name="Powers1991"/>