thumb|Animasjon av Quicksort. De horisontal linjene er «dreietappen», verdier under sortering. Kvikksortering (engelsk: quicksort, 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 sammenligninger for å sortere n elementer. I verste tilfelle krever algoritmen sammenligninger, selv om dette forekommer sjeldent. Klassisk quicksort krever i gjennomsnitt antall sammenligninger og 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 .
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 , 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å 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.
Algoritme right|200px|thumb|Eksempel på Lomutos variant av quicksort på en tilfeldig mengde tall. De gråe elementer er «dreietappen», og blir alltid valgt som siste element i partisjonen. Versjoner av quicksort som velger «dreietappen» som midterste element kjører mye raskere enn Lomutos metode. Quicksort er en «splitt-og-hersk-algoritme». Algoritmen deler først en tabell (eller liste) opp i to mindre undertabeller (eller underlister), som inneholder de laveste elementer og høyere elementer. Deretter blir undertabellene sortert rekursivt.
Trinnene i algoritmen er:
Plukk et element, kalt «dreietapp» (pivot), fra tabellen Partisjoner tabellen slik at alle elementer med lavere verdi enn «dreietappen» går forut for denne, mens verdier som er større kommer etter denne (like verdier kan gå i hver retning). Etter partisjoneringen er «dreietappen» i sin endelige posisjon. Dette kalles partisjons-operasjonen. Anvend trinnene ovenfor rekursivt på undertabellene med mindre elementer og deretter separat på undertabellene med større elementer
Det enkleste tilfelle av rekursjon er tabeller av størrelse 0 eller 1, som aldri trenger å sorteres.
Valg av «dreietapp» og partisjonering kan gjøres på flere måter, og valget av implementasjonsmetode har stor påvirkning på algoritmens ytelse.
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 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 til 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 .
Hoares metode thumb|300px|Animasjon av Lomuto's metode thumb|300px|Animasjon av Hoare's 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 i stedet for . 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 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 og i stedet for og 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]
Jaroslavskijs metode Jaroslavskijs metode benytter to «dreietapper». Den partisjonerer den usorterte tabellen , hvor er en primitiv type (heltall, flyttall, byte, tegn, dobbel, langt heltall og kort heltall) som defineres av to «dreietapper» og . Det er derfor tre pekere, , , , og to indekser, and , som peker på henholdsvis det første og det siste elementet. Algoritmen består av følgende trinn:
For mindre tabeller (lengde < 27) bruk innstikksortering Velg to «dreietapper» og . Vi kan for eksempel, velge det første elementet som og det siste elementet som må være mindre enn . I motsatt fall må de byttes om. Det er derfor fire deler: del 1 som indekserer fra til , med elementer som er mindre enn del 2 som indekserer fra til , med elementer som er større enn eller lik og mindre enn eller lik del 3 som indekserer fra til med elementer som er større enn del 4 inneholder resten av indeksene fra til Det neste elementet ved i del 4 blir sammenlignet med de to «dreiebenkene» og , og plasseres i den korresponderende del 1, del 2, eller del 3 Pekerne , og forandres i de korresponderende retninger Trinnene 4 og 5 blir repetert så lenge «Dreietappen» blir byttet med det siste elementet fra del 1, og «dreietappen» blir byttet med det siste elementet fra del 3