Kvikksortering

**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

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  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 
  public static void sort(int[] a) {
     sort(a, 0, a.length);
  }

  public static void sort(int[] a, int fromIndex, int toIndex) {
     rangeCheck(a.length, fromIndex, toIndex);
     dualPivotQuicksort(a, fromIndex, toIndex - 1, 3);
  }

  private static void rangeCheck(int length, int fromIndex, int toIndex) {
    if (fromIndex > toIndex) {
       throw new IllegalArgumentException("fromIndex > toIndex");
    }
    if (fromIndex  length) {
       throw new ArrayIndexOutOfBoundsException(toIndex);
    }
  }

  private static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

  private static void dualPivotQuicksort(int[] a, int left,int right, int div) {
    int len = right - left; 
    if (len  left && a[j] = right) {
       m2 = right - 1;
    }
    if (a[m1]  pivot2) {
       while (k  pivot2) {
       great--;
       }
       swap(a, k, great--);
       if (a[k]  len - 13 && pivot1 != pivot2) {
        for (int k = less; k 

### 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. 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  er

:.

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

: 

(der  er binomialkoeffisienten) på bekostninga av en forventet økning av bytter. En mer kraftig regel for valg av «dreietapp», for større tabeller, er å velge *ninther*, en rekursiv «median-av-tre» (Mo3), definert som:

:

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  forårsake overflyt og gi en feilaktig «dreietapp»-indeks. Dette kan bli unngått ved å bruke, for eksempel,  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 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  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 \textstyle\sum_{i=0}^n (n-i) = O(n^2), slik at i dette tilfellet krever Quicksort et tidsforbruk på .

#### 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  nøstede kall før vi kommer til en liste av størrelse 1. Dette betyr at dybden av kallstakken er . 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 . Hvert av kallene har en viss konstant overhead, men ettersom det bare er  kall på hvert nivå, er dette tatt hensyn til i faktoren . Resultatet er at algoritmen bare bruker en tid på .

#### Analyse av gjennomsnittlig tilfelle
For å sortere en liste på *n* distinkte elementer, krever quicksort en forventet tid på , i gjennomanitt på alle  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 -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  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 , og hvert nivå av kalltreet prosesserer på det meste *n* elementer, da vil den totale mengden med arbeid i gjennomsnitt være . 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

## Se også
* Boblesortering
* Flettesortering
* Haugsortering

## Referanser




## Litteratur
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
*