Redigerer Kvikksortering

[[Fil:Sorting quicksort anim.gif|thumb|[[Animasjon]] av Quicksort. De horisontal linjene er «dreietappen», verdier under sortering.]]
'''Kvikksortering'''<ref>{{Kilde oppslagsverk|tittel=sorteringsalgoritme|url=https://snl.no/sorteringsalgoritme|oppslagsverk=Store norske leksikon|dato=2023-01-27|besøksdato=2023-03-03|språk=no|fornavn=Pål Grønås|etternavn=Drange}}</ref><ref>{{Kilde www|url=https://www.cs.hioa.no/~ulfu/appolonius/kap1/kap1.html|tittel=Algoritmer og datastrukturer - Kapittel 1   –   |besøksdato=2023-03-03|verk=www.cs.hioa.no}}</ref><ref>{{Kilde www|url=https://hvl.instructure.com/courses/18317/files/1772920/download?download_frd=1|tittel=Algoritmer og datastrukturer - Kapittel 1}}</ref> (engelsk: quicksort, også kalt ''partition-exchange sort'') er en [[algoritmisk effektivitet|effektiv]] [[sorteringsalgoritme]] som benyttes som en systematisk metode for å plassere elementene i en [[liste]] eller en [[Tabell (datastruktur)|tabell]] i rekkefølge. [[Algoritme]]n ble utviklet av den [[Storbritannia|britiske]] [[informatikk|informatikeren]] [[Tony Hoare]] i 1959 mens han var utvekslingsstudent ved [[statsuniversitetet i Moskva]] i [[Sovjetunionen]].<ref name="CHM2017"/> Hans arbeide ble publisert i juli 1961 i det [[vitenskapelig tidsskrift|vitenskapelige tidsskriftet]] ''[[Communications of the ACM]]'' i [[New York]].<ref name="Hoare1961"/> 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]].<ref name="Skiena2008-129"/>

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 [[sorteringsalgoritme|stabil sortering]], noe som betyr at den relative rekkefølgen til sorterte elementer ikke blir bevart. Quicksort kan derfor operere [[på-stedet algoritme|på-stedet]] i en tabell eller liste, noe som krever små tilleggsmengder av [[datalager|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.

[[Analyser av algoritmer|Matematisk analyse]] viser at quicksort [[det beste, verste og gjennomsnittlige tilfelle|i gjennomsnitt]] krever {{math|[[Stor O-notasjon|O]] (''n''&nbsp;log&nbsp;''n'')}} sammenligninger for å sortere ''n'' elementer. I verste tilfelle krever algoritmen {{math|''O''(''n''<sup>2</sup>)}} sammenligninger, selv om dette forekommer sjeldent. Klassisk quicksort krever i gjennomsnitt {{math|2 * ''n'' * ''ln(n)'')}} antall sammenligninger og {{math|1 * ''n'' * ''ln(n)'')}} antall bytter av elementer.<ref name="Jaroslavskij2009"/> Den [[russland|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 {{math|0.8 * ''n'' * ''ln(n)'')}}.<ref name="Jaroslavskij2009"/>

==Historie==
[[Algoritme]]n quicksort ble utviklet av den [[Storbritannia|britiske]] [[informatikk|informatikeren]] [[Tony Hoare]] i 1959 mens han var utvekslingsstudent ved [[statsuniversitetet i Moskva]] i [[Sovjetunionen]].<ref name="CHM2017"/> 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 [[russisk]]e 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]].<ref name="Shustek2009"/> 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 [[autokode]]n ''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åk]]et [[ALGOL (programmeringsspråk)|ALGOL]], og dets evne til å foreta [[rekursjon]]. Dette gjorde han i juli 1961 istand til å publisere koden i det [[vitenskapelig tidsskrift|vitenskapelige tidsskriftet]] ''[[Communications of the ACM]]'', som ble utgitt av [[Association for Computing Machinery]] i [[New York]].<ref name="Hoare1961"/><ref name="DeBarros2015"/>

Quicksort oppnådde raskt en stor utbredelse. I [[Forsknings-Unix|UNIX versjon 3]] (1973) ble algoritmen en del av sorteringsfunksjonen til standardbiblioteket i form av en rutine skrevet i [[assembler]].<ref name="Bell1972"/> I [[UNIX versjon 6]] (1975) ble en variant av quicksort skrevet av R. S. Scowen i standard [[C (programmeringsspråk)|K&R C]],<ref name="Bentley1993"/> og i 1983 ble algoritmen omskrevet for Unix-avarten [[Berkeley Software Distribution]].<ref name="Bentley1993"/> Algoritmen ble i 1973 implementert i [[C-standardbiblioteket]] i form av funksjonen {{mono|[[qsort]]}},<ref name="Wild2013"/> og i 1989 ble den standard i [[ANSI C]]/C90. Funksjonen er også en del av referanseimplementasjonen av [[Java (programmeringsspråk)|Java]].<ref name="Wild2013"/>

Den [[USA|amerikanske]] [[informatikk|informatikeren]] [[Robert Sedgewick]] ved [[Stanford University]], [[California]], publiserte i 1975 en [[doktoravhandling]] som blir betraktet som en milepæl innenfor studiet av quicksort.<ref name="Sedgewick1980"/> I denne avhandlingen løste han mange [[åpent problem|åpne problemer]] relatert til analyser av ulike måter å bruke «dreietapper» (''pivot'') på, deriblant [[samplesort]], adaptiv partisjonering av Maarten H. van Emden<ref name="Emden1970"/> så vel som derivasjoner av forventede antall sammenligninger og bytter.<ref name="Bentley1993"/> [[Jon Bentley]] fra [[Carnegie Mellon University]] i [[Pittsburgh]], [[Pennsylvania]], og [[Doug McIlroy|Malcolm McIlroy]] fra [[Massachusetts Institute of Technology]] inkorporerte i 1993 flere forbedringer for quicksort, til bruk for [[Bibliotek (programvare)|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 [[median]]en av alle tre medianer i de tre gruppene blir valgt.<ref name="Bentley1993"/> 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.<ref name="Oram2007"/> 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å {{math|''O''(''n''<sup>2</sup>)}} når alle elementene er identiske.<ref name="CS2017"/>

I 2009 foreslo den [[Russland|russiske]] informatikeren Vladimir Jaroslavskij en ny dobbel «dreietapp»-implementasjon av quicksort.<ref name="Jaroslavskij2009"/> I [[e-postliste]]n 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.<ref name="HN1999"/> Hans versjon av quicksort ble i 2011 valgt som standard sorteringsalgoritme i versjon 7 av [[Oracle (selskap)|Oracle Corporation]]s runtimebibliotek for Java etter omfattende empiriske ytelsestester.<ref name="Wild2013"/>

==Algoritme==
[[Fil:Quicksort-diagram.svg|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 [[rekursjon|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'',<ref name="Bentley1999"/> og av [[Thomas H. Cormen]] med flere i boken ''Introduction to Algorithms''.<ref name="Cormen2009"/> 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.<ref name="Wild2012"/> I verste tilfelle krever denne metoden {{math|''O''(''n''<sup>2</sup>)}} sammenligninger. Det skjer når tabellen allerede er sortert eller når den bare har identiske elementer.<ref name="CS2017"/> 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 {{mono|lo}} til {{mono|hi}} i en tabell ''A'' bli uttrykt på følgende måte:<ref name="Cormen2009_170-190"/>

 '''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 {{mono|quicksort(A, 1, lengde(A))}}.

===Hoares metode===
[[Fil:Lomuto animated.gif|thumb|300px|Animasjon av Lomuto's metode]]
[[Fil:Quicksort-example.gif|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.<ref name="Hoare1962"/> Når indeksene møtes, vil algoritmen stoppe og returnere den endelige indeks. Det finnes mange varianter av denne algoritmen, deriblant å velge «dreietapp» fra {{mono|A[hi]}} i stedet for {{mono|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.<ref name="CS2017"/> Hoares partisjonering vil, liksom Lomuto's metode, kreve {{math|''O''(''n''<sup>2</sup>)}} 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 {{mono|(lo..p)}} og {{mono|(p+1..hi)}} i stedet for {{mono|(lo..p-1)}} og {{mono|(p+1..hi)}} som tilfellet er i Lomuto's metode. I pseudokode blir Hoares metode slik:<ref name="Cormen2009_170-190"/>

 '''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».<ref name="Jaroslavskij2009"/> Den partisjonerer den usorterte tabellen {{mono|'''T [] a'''}}, hvor {{mono|'''T'''}} er en primitiv type ([[heltall]], [[flyttall]], [[byte]], [[tegn]], [[dobbelpresisjons flyttallsformat|dobbel]], langt heltall og kort heltall) som defineres av to «dreietapper» {{mono|'''P1'''}} og {{mono|'''P2'''}}. Det er derfor tre pekere, {{mono|'''L'''}}, {{mono|'''K'''}}, {{mono|'''G'''}}, og to indekser, {{mono|'''left'''}} and {{mono|'''right'''}}, som peker på henholdsvis det første og det siste elementet.<ref name="Jaroslavskij2009"/> Algoritmen består av følgende trinn:<ref name="Jaroslavskij2009"/>

# For mindre tabeller (lengde < 27) bruk innstikksortering
# Velg to «dreietapper» {{mono|'''P1'''}} og {{mono|'''P2'''}}. Vi kan for eksempel, velge det første elementet {{mono|'''a[left]'''}} som {{mono|'''P1'''}} og det siste elementet {{mono|'''a[right]'''}} som {{mono|'''P2'''}}
# {{mono|'''P1'''}} må være mindre enn {{mono|'''P2'''}}. I motsatt fall må de byttes om. Det er derfor fire deler:
##del 1 som indekserer fra {{mono|'''left+1'''}} til {{mono|'''L-1'''}}, med elementer som er mindre enn {{mono|'''P1'''}}
##del 2 som indekserer fra {{mono|'''L'''}} til {{mono|'''L-1'''}}, med elementer som er større enn eller lik {{mono|'''P1'''}} og mindre enn eller lik {{mono|'''P2'''}}
##del 3 som indekserer fra {{mono|'''G+1'''}} til {{mono|'''right–1'''}} med elementer som er større enn {{mono|'''P2'''}}
##del 4 inneholder resten av indeksene fra {{mono|'''K'''}} til {{mono|'''G'''}}
#Det neste elementet ved {{mono|'''a[left]'''}} i del 4 blir sammenlignet med de to «dreiebenkene» {{mono|'''P1'''}} og {{mono|'''P2'''}}, og plasseres i den korresponderende del 1, del 2, eller del 3
#Pekerne {{mono|'''L'''}}, {{mono|'''K'''}} og {{mono|'''G'''}} forandres i de korresponderende retninger
#Trinnene 4 og 5 blir repetert så lenge {{mono|'''K ≤ G'''}}
#«Dreietappen» {{mono|'''P1'''}} blir byttet med det siste elementet fra del 1, og «dreietappen» {{mono|'''P2'''}} blir byttet med det siste elementet fra del 3
# Trinn 1-7 blir gjentatt rekursivt for hver enkelt del, del 1, del 2 og del 3

Her er koden for Jaroslavskijs metode, skrevet i programmeringsspråket Java:<ref name="Jaroslavskij2009"/>

<syntaxhighlight lang="C">
  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 < 0) {
       throw new ArrayIndexOutOfBoundsException(fromIndex);
    }
    if (toIndex > 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 < 27) { // insertion sort for tiny array
      for (int i = left + 1; i <= right; i++) {
        for (int j = i; j > left && a[j] < a[j - 1]; j--) {
          swap(a, j, j - 1);
        }
      }
    return;
    }
    int third = len / div;
    // «medianer»
    int m1 = left + third;
    int m2 = right - third;

    if (m1 <= left) {
       m1 = left + 1;
    }
    if (m2 >= right) {
       m2 = right - 1;
    }
    if (a[m1] < a[m2]) {
      swap(a, m1, left);
      swap(a, m2, right);
    } else {
     swap(a, m1, right);
     swap(a, m2, left);
    }

    // dreietapper
    int pivot1 = a[left];
    int pivot2 = a[right];

    // pekere
    int less = left + 1;
    int great = right - 1;

  // sortering
    for (int k = less; k <= great; k++) {
       if (a[k] < pivot1) {
       swap(a, k, less++);
    }
    else if (a[k] > pivot2) {
       while (k < great && a[great] > pivot2) {
       great--;
       }
       swap(a, k, great--);
       if (a[k] < pivot1) {
          swap(a, k, less++);
       }
    }
  }
  // ombyttinger
  int dist = great - less;

  if (dist < 13) {
     div++;
  }
  swap(a, less - 1, left);
  swap(a, great + 1, right);
  // undertabeller
  dualPivotQuicksort(a, left, less - 2, div);
  dualPivotQuicksort(a, great + 2, right, div);
  // like elementer
     if (dist > len - 13 && pivot1 != pivot2) {
        for (int k = less; k <= great; k++) {
        if (a[k] == pivot1) {
          swap(a, k, less++);
        } else if (a[k] == pivot2) {
            swap(a, k, great--);
        if (a[k] == pivot1) {
           swap(a, k, less++);
        }
      }
    }
  }
  // undertabeller
  if (pivot1 < pivot2) {
    dualPivotQuicksort(a, less, great, div);
  }
  }
</syntaxhighlight>

===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"/>

===Formell analyse===
==== Analyse av verste tilfelle ====
Den mest ubalanserte posisjon inntreffer når «dreiepinnen» deler listen opp i to underlister med størrelsene {{math|0}} og {{math|''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 {{mono|'''{{math|''n'' − 1}}'''}} nøstede kall før vi kommer til en liste av størrelse 1. Dette betyr at [[kallstakk]]en er en lineær kjede av {{mono|'''{{math|''n'' − 1}}'''}} nøstede kall. Kall nr ''i'' foretar {{mono|'''{{math|''O''(''n'' − ''i'')}}'''}} arbeid på partisjonen, og <math>\textstyle\sum_{i=0}^n (n-i) = O(n^2)</math>, slik at i dette tilfellet krever Quicksort et tidsforbruk på {{mono|'''{{math|''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 {{mono|'''{{math|log<sub>2</sub> ''n''}}'''}} nøstede kall før vi kommer til en liste av størrelse 1. Dette betyr at dybden av kallstakken er {{mono|'''{{math|log<sub>2</sub> ''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 {{mono|'''{{math|''O''(''n'')}}'''}}. Hvert av kallene har en viss konstant overhead, men ettersom det bare er {{mono|'''{{math|''O''(''n'')}}'''}} kall på hvert nivå, er dette tatt hensyn til i faktoren {{mono|'''{{math|''O''(''n'')}}'''}}. Resultatet er at algoritmen bare bruker en tid på {{mono|'''{{math|''O''(''n'' log ''n'')}}'''}}.

==== 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}}

== Se også ==
* [[Boblesortering]]
* [[Flettesortering]]
* [[Haugsortering]]

==Referanser==
<references>

<ref name="Acar2013">[[#Acar2013|Acar 2013]]</ref>
<ref name="Bell1972">[[#Bell1972|Bell 1972]]</ref>
<ref name="Bentley1993">[[#Bentley1999|Bentley 1993]]</ref>
<ref name="Bentley1999">[[#Bentley1999|Bentley 1999]]</ref>
<ref name="Bentley1999_117">[[#Bentley1999|Bentley 1999]], side 117</ref>
<ref name="Breshears2012">[[#Breshears2012|Breshears 2012]]</ref>
<ref name="CHM2017">[[#CHM2017|Computer History Museum 2017]]</ref>
<ref name="CS2017">[[#CS2017|Computer Science 2017]]</ref>
<ref name="Cormen2009">[[#Cormen2009|Cormen 2009]]</ref>
<ref name="Cormen2009_170-190">[[#Cormen2009|Cormen 2009]], side 170-190</ref>
<ref name="Emden1970">[[#Emden1970|van Emden 1970]]</ref>
<ref name="DeBarros2015">[[#DeBarros2015|DeBarros 2015]]</ref>
<ref name="GNUC2017">[[#GNUC2017|GNU C 2017]]</ref>
<ref name="HN1999">[[#HN1999|Hacker News 1999]]</ref>
<ref name="Hoare1961">[[#Hoare1961|Hoare 1961]]</ref>
<ref name="Hoare1962">[[#Hoare1962|Hoare 1962]]</ref>
<ref name="Jaroslavskij2009">[[#Jaroslavskij2009|Jaroslavskij 2009]]</ref>
<ref name="LaMarca1999">[[#LaMarca1999|LaMarca 1999]]</ref>
<ref name="Miller2000">[[#Miller2000|Miller 2000]]</ref>
<ref name="Oram2007">[[#Oram2007|Oram 2007]]</ref>
<ref name="Powers1991">[[#Powers1991|Powers 1991]]</ref>
<ref name="Sedgewick1978">[[#Sedgewick1978|Sedgewick 1978]]</ref>
<ref name="Sedgewick1980">[[#Sedgewick1980|Sedgewick 1980]]</ref>
<ref name="Sedgewick1998">[[#Sedgewick1998|Sedgewick 1998]]</ref>
<ref name="Skiena2008-129">[[#Skiena2008|Skiena 2008]], side 129</ref>
<ref name="Shustek2009">[[#Shustek2009|Shustek 2009]]</ref>
<ref name="Wild2012">[[#Wild2012|Wild 2012]]</ref>
<ref name="Wild2013">[[#Wild2013|Wild 2013]]</ref>

</references>

==Litteratur==
* {{Kilde bok
  | ref=Acar2013
  | forfatter=Acar, Umut A.; [[Guy Blelloch|Blelloch, Guy E.]]; Reid-Miller, Margaret; Tangwongsan, Kanat 
  | utgivelsesår=2013
  | tittel= Quicksort and Sorting Lower Bounds
  | url=http://www.cs.cmu.edu/afs/cs/academic/class/15210-s13/www/lectures/lecture19.pdf
  | forlag=Parallel and Sequential Data Structures and Algorithms, 15-210, våren 2013.
}}
* {{Kilde bok
  | ref=Bell1972
  | forfatter=[[Bell Laboratories]]
  | utgivelsesår=1972
  | tittel= QSORT (III)
  | url=http://minnie.tuhs.org/cgi-bin/utree.pl?file=V3/man/man3/qsort.3
  | forlag=V3/man/man3/qsort3, UNIX Programmer's Manual, Third Edition, 6. desember 1972
  | isbn=
  | id=
}}
* {{Kilde bok
  | ref=Bentley1993
  | forfatter=[[Jon Bentley|Bentley, Jon Louis]]; [[Doug McIlroy|McIlroy, Douglas Malcolm]]
  | utgivelsesår=1993
  | tittel= Engineering a sort function
  | url=http://onlinelibrary.wiley.com/doi/10.1002/spe.4380231105/abstract
  | forlag=Software: Practice and Experience, Volume 23, Issue 11, november 1993
  | side=1249-1265
  | id=doi:10.1002/spe.4380231105
}}
* {{Kilde bok
  | ref=Bentley1999
  | forfatter=Bentley, Jon Louis
  | utgivelsesår=1999
  | tittel=Programming Pearls
  | forlag=[[Addison-Wesley|Addison-Wesley Professional]]; 2. utgave, 7. oktober 1999
  | isbn=0 2016 5788 0
  | id=ISBN 978 0 20165 788 3
}}
* {{Kilde bok
  | ref=Breshears2012
  | forfatter=Breshears, Clay 
  | utgivelsesår=2012
  | tittel= Quicksort Partition via Prefix Scan
  | url=http://www.drdobbs.com/parallel/quicksort-partition-via-prefix-scan/240003109
  | forlag=Dr. Dobb’s Journal. The World of Software Development, 2. juli 2012.
}}
* {{Kilde bok
  | ref=CHM2017
  | forfatter=[[Computer History Museum]]
  | utgivelsesår=2017
  | tittel= Sir Antony Hoare
  | url=http://www.computerhistory.org/fellowawards/hall/sir-antony-hoare/
  | forlag=2006 Fellow, Hall of Fellows, 2017, besøkt 30. januar 2017
  | id=
}}
* {{Kilde bok
  | ref=CS2017
  | forfatter=Computer Science
  | utgivelsesår=2017
  | tittel= Quicksort Partitioning: Hoare vs. Lomuto
  | url=http://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto/11550#11550
  | forlag=besøkt 31. januar 2017
}}
* {{Kilde bok
  | ref=Cormen2009
  | forfatter=[[Thomas H. Cormen|Cormen, Thomas H.]]; [[Charles E. Leiserson|Leiserson, Charles Eric]]; [[Ron Rivest|Rivest, Ronald Linn]]; [[Clifford Stein|Stein, Clifford Seth]]
  | utgivelsesår=2009
  | tittel=[[Introduction to Algorithms]]
  | forlag=[[MIT Press|The MIT Press]]; 3. utgave, 31. juli 2009
  | isbn=0 2620 3384 4
  | id=ISBN 978 0 26203 384 8
}}
* {{Kilde bok
  | ref=DeBarros2015
  | forfatter=De Barros, Marcelo M.
  | utgivelsesår=2015
  | tittel= My Quickshort interview with Sir Tony Hoare, the inventor of Quicksort
  | url=http://anothercasualcoder.blogspot.com/2015/03/my-quickshort-interview-with-sir-tony.html
  | forlag=anothercasualcoder.blogspot.com, blogg, 15. mars 2015
}}
* {{Kilde bok
  | ref=Emden1970
  | forfatter=van Emden, Maarten H.; Mathematical Center, [[Amsterdam]], [[Nederland]]
  | utgivelsesår=1970
  | tittel=  Algorithms 402: Increasing the Efficiency of Quicksort
  | url=http://doi.acm.org/10.1145/362790.362803
  | forlag=[[Communications of the ACM]], Volume 13, Issue 11, [[New York]], november 1970
  | side=693-694 
  | id=doi:10.1145/362790.362803, ISSN 0001-0782
}}
* {{Kilde bok
  | ref=GNUC2017
  | forfatter=GNU C
  | utgivelsesår=2017
  | tittel= qsort
  | url=http://repo.or.cz/w/glibc.git/blob/HEAD:/stdlib/qsort.c
  | forlag=GNU C Library (glibc), 2017, besøkt 1. februar 2017
}}
* {{Kilde bok
  | ref=HN1999
  | forfatter=Hacker News
  | utgivelsesår=1999
  | tittel= Potential Quicksort replacement in java.util.Arrays with new Dual-Pivot
  | url=http://doi.acm.org/10.1145/362790.362803
  | forlag=doi.acm.org, Hacker News, oktober 1999
}}
* {{Kilde bok
  | ref=Hoare1961
  | forfatter=[[Tony Hoare|Hoare, C. A. R.]], [[Elliott Brothers|Elliott brothers Ltd.]], [[Hertfordshire]], [[England]], U.K.  
  | utgivelsesår=1961
  | tittel= Algorithm 64: Quicksort
  | url=http://dl.acm.org/citation.cfm?doid=366622.366644
  | forlag=Communications of the ACM, Volume 4, Issue 7, [[New York]], juli 1961
  | side=321 
  | id=doi 10.1145/366622.366644
}}
* {{Kilde bok
  | ref=Hoare1962
  | forfatter=Hoare, C. A. R.
  | utgivelsesår=1962
  | tittel= Quicksort
  | url=https://academic.oup.com/comjnl/article-abstract/5/1/10/395338/Quicksort?redirectedFrom=fulltext
  | forlag=The Computer Journal, Volume 5, Issue 1, [[Oxford]], 1. januar 1962
  | side=10-16
  | id=DOI: https://doi.org/10.1093/comjnl/5.1.10
}}
* {{Kilde bok
  | ref=Jaroslavskij2009
  | forfatter=Jaroslavskij, Vladimir
  | utgivelsesår=2009
  | tittel= Dual-Pivot Quicksort
  | url=http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf
  | forlag= 6. februar 2009
}}
* {{Kilde bok
  | ref=LaMarca1999
  | forfatter=LaMarca, Anthony; Ladner, Richard E.;[[PARC|Xerox PARC]], 3333 Coyote Hill Road, [[Palo Alto]], [[California]], 94304
  | utgivelsesår=1999
  | tittel= The Influence of Caches on the Performance of Sorting
  | url=http://www.sciencedirect.com/science/article/pii/S0196677498909853?via%3Dihub
  | forlag=Journal of Algorithms, Volume 31, Issue 1, April 1999
  | side=66–104
  | id=doi:10.1006/jagm.1998.0985.
}}
* {{Kilde bok
  | ref=Miller2000
  | forfatter=Miller, Russ; Boxer, Laurence
  | utgivelsesår=2000
  | tittel= Algorithms sequential & parallel: a unified approach
  | url=https://books.google.no/books?id=dZoZAQAAIAAJ&redir_esc=y
  | forlag=[[Prentice Hall]], 2000
  | isbn=0 1308 6373 4
  | id=ISBN 978 0 13 086373 7
}}
* {{Kilde bok
  | ref=Oram2007
  | forfatter=Oram, Andy; Wilson, Greg
  | utgivelsesår=1980
  | tittel=Beautiful Code: Leading Programmers Explain How They Think (Theory in Practice) 
  | forlag=Chapter 3; O'Reilly Media; 6. juli 2007
  | side=30
  | isbn=0 5965 1004 7
  | id=ISBN 978 0 59651 004 6
}}
* {{Kilde bok
  | ref=Powers1991
  | forfatter=Powers, David M. W.
  | utgivelsesår=1991
  | tittel=Parallelized Quicksort and Radixsort with Optimal Speedup
  | url=https://pdfs.semanticscholar.org/ff57/e3eb7cb246bbd0fada5c563d6f9bc35747fd.pdf
  | forlag=Proceedings of the International Conference on Parallel on Parallel Computing Technologies, Universität Kaiserslautern, [[Kaiserslautern]], [[Vest-Tyskland]], 1991
  | besøksdato=2017-02-02
  | arkiv-dato=2017-02-03
  | arkiv-url=https://web.archive.org/web/20170203160929/https://pdfs.semanticscholar.org/ff57/e3eb7cb246bbd0fada5c563d6f9bc35747fd.pdf
  | url-status=død
  }}
* {{Kilde bok
  | ref=Sedgewick1978
  | forfatter=[[Robert Sedgewick|Sedgewick, Robert]]
  | utgivelsesår=1978
  | tittel= Implementing Quicksort programs
  | url=http://dl.acm.org/citation.cfm?doid=359619.359631
  | forlag=[[Communications of the ACM]], Volume 21, Issue 10, New York, oktober 1978
  | side=847-857
  | id=doi:10.1145/359619.359631.
}}
* {{Kilde bok
  | ref=Sedgewick1980
  | forfatter=Sedgewick, Robert
  | utgivelsesår=1980
  | tittel=Quicksort
  | forlag=[[Garland Science|Garland Publishing, Inc.]]; 1. april 1980
  | isbn=0 8240 4417 7
  | id=ISBN 978 0 82404 417 6
}}
* {{Kilde bok
  | ref=Sedgewick1998
  | forfatter=Sedgewick, Robert
  | utgivelsesår=1998
  | tittel=Algorithms In C : Fundamentals, Data Structures, Sorting, Searching, Parts 1-4
  | forlag=Pearson; 3. utgave, 1. september 1998
  | isbn=8 1317 1291 5
  | id=ISBN 978 8 13171 291 7
}}
* {{Kilde bok
  | ref=Shustek2009
  | forfatter=[[Len Shustek|Shustek, Leonard J.]]; Computer History Museum, Mountain View, CA
  | utgivelsesår=2009
  | tittel=Interview: An interview with C.A.R. Hoare
  | forlag=Communications of the ACM, Volume 52, Issue 3, New York, mars 2009
  | side=38-41
  | isbn=
  | id=doi 10.1145/1467247.1467261
}}
* {{Kilde bok
  | ref=Skiena2008
  | forfatter=[[Steven Skiena|Skiena, Steven Sol]]
  | utgivelsesår=2008
  | tittel= The Algorithm Design Manual
  | url=https://books.google.no/books?id=7XUSn0IKQEgC&redir_esc=y
  | forlag=[[Springer Publishing]]; 2. utgave, 26. juli 2008
  | isbn=1 8480 0069 3
  | id=ISBN 978 1 84800 069 8
}}
* {{Kilde bok
  | ref=Wild2012
  | forfatter=Wild, Sebastian
  | utgivelsesår=2012
  | tittel= Engineering Java 7's Java 7's Dual Pivot Quicksort
  | url=https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3463
  | forlag=Technische Universität Kaiserslautern, KLUEDO, 2012
  | id=doi: 10.1137/1.9781611972931.5.
}}
* {{Kilde bok
  | ref=Wild2013
  | forfatter=Wild, Sebastian; Nebel, Markus; Reitzig, Raphael; Laube, Ulrich
  | utgivelsesår=2013
  | tittel= Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn*: Adventures with Just-In-Time Compilation
  | url=http://epubs.siam.org/doi/abs/10.1137/1.9781611972931.5
  | forlag=2013 Proceedings of the Fifteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics (SIAM); 7. januar 2013
  | side=55–69, doi: 10.1137/1.9781611972931.5.
  | isbn=978 1 61197 253 5
  | id=ISBN 978 1 61197 293 1 
}}

{{Autoritetsdata}}

[[Kategori:Quicksort| ]]