Quicksort

Quicksort (på engelsk også kalt partition-exchange sort) er en effektiv sorteringsalgoritme som benyttes som en systematisk metode for å plassere elementene i en liste eller en tabell i rekkefølge. Algoritmen ble utviklet av den britiske informatikeren Tony Hoare i 1959 mens han var utvekslingsstudent ved statsuniversitetet i Moskva i Sovjetunionen. Hans arbeide ble publisert i juli 1961 i det vitenskapelige tidsskriftet Communications of the ACM i New York. Quicksort blir fortsatt benyttet som en vanlig algoritme for sortering. Når den implementeres på rette måten, kan den være 2-3 ganger raskere enn flettesortering og haugsortering.
Quicksort er en form for sammenligningsortering. Algoritmen kan sortere elementer av enhver type hvor «mindre-enn» relasjonen (formelt en total orden) er definert. I effektive implementasjoner er den ikke en stabil sortering, noe som betyr at den relative rekkefølgen til sorterte elementer ikke blir bevart. Quicksort kan derfor operere på-stedet i en tabell eller liste, noe som krever små tilleggsmengder av dataminne for å utføre sorteringen.
Quicksort er en «splitt og hersk-algoritme». Den begynner med å velge et tilfeldig tall x i datasettet, kalt en «dreietapp» (pivot). Deretter sorteres settet i tre deler, en del for de tallene som er mindre enn x, en del for dem som er like store, og en del for dem som er større. Operasjonen gjentas gjennom rekursjon på de tallene som er større og de tallene som er mindre, inntil alle tall er sortert i rekkefølge.
Matematisk analyse viser at quicksort i gjennomsnitt krever O (n log n) sammenligninger for å sortere n elementer. I verste tilfelle krever algoritmen O(n²) sammenligninger, selv om dette forekommer sjeldent. Klassisk quicksort krever i gjennomsnitt 2 * n * ln(n)) antall sammenligninger og 1 * n * ln(n)) antall bytter av elementer. Den russiske informatikeren Vladimir Jaroslavskij foreslo i 2009 en raskere variant av quicksort. Det gjennomsnittlige antallet sammenligninger er det samme i den nye algoritmen, men antallet bytter av elementer er kun 0.8 * n * ln(n)).

Historie

Algoritmen quicksort ble utviklet av den britiske informatikeren Tony Hoare i 1959 mens han var utvekslingsstudent ved statsuniversitetet i Moskva i Sovjetunionen. På denne tiden arbeidet Hoare innenfor et prosjekt for maskinoversettelse som ble utført i regi av National Physical Laboratory i Teddington, London. Under oversettelsen trengte han å sortere ord i russiske setninger før han slo opp på ordene i en russisk-engelsk ordbok som allerede var sortert i alfabetisk rekkefølge på et magnetbånd. Hans første idé var å benytte innstikksortering, men etter å ha innsett at denne ville være treg, fikk han snart idéen om en ny sorteringsalgoritme som var quicksort. Han skrev et program i autokoden Mercury for partisjonen av ord, men klarte ikke å lage programmet slik at det tok hensyn til listen av usorterte segmenter. Da han kom tilbake til England ble han bedt om å skrive en kode for Shellsortering som del av hans nye jobb. Hoare nevnte for sin sjef at han visste om en raskere algoritme, men ble ikke trodd: Sjefen veddet en sixpence på at han ikke gjorde det, men ble til slutt nødt til å akseptere at han hadde tapt veddemålet. Senere lærte Hoare om programmeringsspråket ALGOL, og dets evne til å foreta rekursjon. Dette gjorde han i juli 1961 istand til å publisere koden i det vitenskapelige tidsskriftet Communications of the ACM, som ble utgitt av Association for Computing Machinery i New York.
Quicksort oppnådde raskt en stor utbredelse. I UNIX versjon 3 (1973) ble algoritmen en del av sorteringsfunksjonen til standardbiblioteket i form av en rutine skrevet i assembler. I UNIX versjon 6 (1975) ble en variant av quicksort skrevet av R. S. Scowen i standard K&R C, og i 1983 ble algoritmen omskrevet for Unix-avarten Berkeley Software Distribution. Algoritmen ble i 1973 implementert i C-standardbiblioteket i form av funksjonen qsort, og i 1989 ble den standard i ANSI C/C90. Funksjonen er også en del av referanseimplementasjonen av Java.
Den amerikanske informatikeren Robert Sedgewick ved Stanford University, California, publiserte i 1975 en doktoravhandling som blir betraktet som en milepæl innenfor studiet av quicksort. I denne avhandlingen løste han mange åpne problemer relatert til analyser av ulike måter å bruke «dreietapper» (pivot) på, deriblant samplesort, adaptiv partisjonering av Maarten H. van Emden så vel som derivasjoner av forventede antall sammenligninger og bytter. Jon Bentley fra Carnegie Mellon University i Pittsburgh, Pennsylvania, og Malcolm McIlroy fra Massachusetts Institute of Technology inkorporerte i 1993 flere forbedringer for quicksort, til bruk for programvarebiblioteker, deriblant en teknikk som håndterer like elementer og en «dreietapp»-metode som er kjent som pseudomedianen av ni, hvor et utvalg av ni elementer deles opp i grupper på tre og medianen av alle tre medianer i de tre gruppene blir valgt. Jon Bentley beskrev senere en annen enklere og mer kompakt metode i boken Programming Pearls, som han tilegnet Nico Lumuto. Senere skrev Bentley at han hadde brukt Hoare’s versjon over mange år, men aldri hadde virkelig forstått den, og at Lomuto's versjon var enkel nok til å vise seg å være korrekt. I det samme essay beskrev han quicksort som «den vakreste koden jeg noensinne har skrevet». Lomuto’s metode ble popularisert gjennom læreboken Introduction to Algorithms som utkom i 1990, selv om den er underlegen Hoare’s metode fordi den foretar tre ganger flere bytter i gjennomsnitt og har en kjøretid på O(n²) når alle elementene er identiske.
I 2009 foreslo den russiske informatikeren Vladimir Jaroslavskij en ny dobbel «dreietapp»-implementasjon av quicksort. I e-postlisten til Javakjernens runtimebibliotek  startet han en diskusjon hvor han hevdet at hans nye algoritme var overlegen bibliotekets sorteringsmetode, som på denne tiden var utbredt, og som benyttet en variant av den klassiske quicksort til Bentley og McIlroy. Hans versjon av quicksort ble i 2011 valgt som standard sorteringsalgoritme i versjon 7 av Oracle Corporations runtimebibliotek for Java etter omfattende empiriske ytelsestester.

Lomutos metode

Denne metoden tilegnes Nico Lomuto og ble popularisert av Bentley i boken Programming Pearls, og av Thomas H. Cormen med flere i boken Introduction to Algorithms. Metoden velger en «dreiepinne» som vanligvis er siste element i tabellen. Algoritmen ivaretar indeksen til «dreiepinnen» i variabelen i, og hver gang den finner et element som er mindre enn eller likt «dreiepinnen» blir denne indeksen inkrementert og dette elementet plasseres foran «dreiepinnen». Denne metoden er mer kompakt og lettere å forstå og er ofte brukt i introduksjoner av algoritmer, men er mindre effektiv enn Hoares opprinnelige metode. I verste tilfelle krever denne metoden O(n²) sammenligninger. Det skjer når tabellen allerede er sortert eller når den bare har identiske elementer. Ulike varianter av metoden har blitt foreslått for å øke ytelsen, deriblant ulike måter å velge «dreiepinne», håndtering av identiske elementer, bruk av andre algoritmer som f.eks. innstikksortering for mindre tabeller, etc. I pseudokode kan en quicksort som sorterer elementer fra lo til hi i en tabell A bli uttrykt på følgende måte:
algoritme quicksort(A, lo, hi) er
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p – 1)
        quicksort(A, p + 1, hi)

algoritme partition(A, lo, hi) er
    dreietapp := A[hi]
    i := lo     // sted for ombytting
    for j := lo to hi – 1 do
        if A[j] ≤ dreietapp then
            bytt om A[i] og A[j]
            i := i + 1
    bytt om A[i] og A[hi]
    return i
Å sortere hele tabellen blir oppnådd gjennom rutinekallet quicksort(A, 1, lengde(A)).

Hoares metode

Den opprinnelige metoden som er beskrevet av C.A.R. Hoare, bruker to indekser som begynner på begge endene av tabellen som partisjoneres, og som deretter beveger seg mot hverandre, inntil de oppdager en inversjon: Et par av elementer, det ene større enn eller identisk med «dreietappen» og det andre mindre eller identisk, som er i feil rekkefølge relativt til hverandre. De inverterte elementene blir deretter byttet om med hverandre. Når indeksene møtes, vil algoritmen stoppe og returnere den endelige indeks. Det finnes mange varianter av denne algoritmen, deriblant å velge «dreietapp» fra A[hi] i stedet for A[lo]. Hoare's metode er mer effektiv enn Lomuto's fordi den foretar tre færre ombyttinger i gjennomsnitt, og fordi den skaper effektive partisjoneringer selv når alle verdier er identiske. Hoares partisjonering vil, liksom Lomuto's metode, kreve O(n²) når den innmatede tabellen allerede er sortert. På samme måte produserer den ikke en stabil sortering. «Dreietappens» endelige lokalisering er ikke nødvendigvis ved indeksen som ble returnert, og de neste to segmenter som hovedalgoritmen frembringer er (lo..p) og (p+1..hi) i stedet for (lo..p-1) og (p+1..hi) som tilfellet er i Lomuto's metode. I pseudokode blir Hoares metode slik:
algoritme quicksort(A, lo, hi) er
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi)

algoritme partition(A, lo, hi) er
    dreietapp := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < dreietapp

        do
            j := j - 1
        while A[j] > dreietapp

        if i >= j then
            return j

        bytt om A[i] og A[j]

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 kvadratisk tid for å sortere en tabell med like verdier.
For å løse dette problemet, som noen ganger blir kalt «det nederlandske flaggets problem», 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 qsort i UNIX versjon 7 (1979). 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 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.

Parallellisering

Quicksorts splitt og hersk-formulering gjør den egnet for parallellisering ved å bruke oppgaveparallellisme. Partisjoneringstrinnet blir oppnådd gjennom bruken av en parallell prefixsum-algoritme for å beregne en indeks for hvert tabellelement i sin seksjon av den partisjonerte tabellen. Dersom vi har en tabell av størrelse n, utfører partisjoneringstrinnet et arbeid på O(n) i tidsrommet O(log n) som krever 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 n med et arbeid på O(n log n) i tidsrommet O(log² n) ved å bruke 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.
Andre mer sofistikerte parallele sorteringsalgoritmer kan oppnå dette innenfor bedre tidsgrenser. I 1991 beskrev for eksempel David Powers en parallellisert quicksort (og en beslektet radixsortering) som kan operere med en tid på O(log n) på en CRCW PRAM (parallel random-access machine) med n mikroprosessorer som utfører partisjonering implisitt.

Analyse av verste tilfelle

Den mest ubalanserte posisjon inntreffer når «dreiepinnen» deler listen opp i to underlister med størrelsene 0 og n − 1. Dette kan inntreffe hvis «dreiepinnen» er det minste eller det største elementet i listen, eller i enkelte implementasjoner (Lomutos metode) når alle elementene er like.
Hvis dette inntreffer gjentatte ganger i hver posisjon, da prosesserer hvert rekursivt kall en liste som er en mindre i størrelse enn den forrige listen. Vi kan foreta n − 1 nøstede kall før vi kommer til en liste av størrelse 1. Dette betyr at kallstakken er en lineær kjede av n − 1 nøstede kall. Kall nr i foretar O(n − i) arbeid på partisjonen, og , slik at i dette tilfellet krever Quicksort et tidsforbruk på O(n²).

Analyse av beste tilfelle

I det mest balanserte tilfelle, deles listen inn i to nesten like store deler hver gang vi utfører en partisjonering. Dette betyr at hvert rekursive kall prosesserer en liste av halve størrelsen, Og vi kan foreta kun log₂ n nøstede kall før vi kommer til en liste av størrelse 1. Dette betyr at dybden av kallstakken er log₂ n. Men to kall på samme nivå av kallstakken prosesserer aldri den samme delen av den samme listen; hvert nivå av kall behøver derfor bare en tid på totalt O(n). Hvert av kallene har en viss konstant overhead, men ettersom det bare er O(n) kall på hvert nivå, er dette tatt hensyn til i faktoren O(n). Resultatet er at algoritmen bare bruker en tid på O(n log n).

Analyse av gjennomsnittlig tilfelle

For å sortere en liste på n distinkte elementer, krever quicksort en forventet tid på O(n log n), i gjennomanitt på alle n! permutasjoner av n elementer 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   ganger før vi fikk lister av størrelse 1, noe som ville medføre en 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 2k 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 . Men hvis gjennomsnittlig kalldybde er 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 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.