Hopp til innhold

Kvikksortering

Fra Wikipedia, den frie encyklopedi
(Omdirigert fra «Quicksort»)
Animasjon av Quicksort. De horisontal linjene er «dreietappen», verdier under sortering.

Kvikksortering[1][2][3] (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.[4] Hans arbeide ble publisert i juli 1961 i det vitenskapelige tidsskriftet Communications of the ACM i New York.[5] 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.[6]

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(n2) 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.[7] 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)).[7]

Historie

[rediger | rediger kilde]

Algoritmen quicksort ble utviklet av den britiske informatikeren Tony Hoare i 1959 mens han var utvekslingsstudent ved statsuniversitetet i Moskva i Sovjetunionen.[4] 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.[8] 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.[5][9]

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.[10] I UNIX versjon 6 (1975) ble en variant av quicksort skrevet av R. S. Scowen i standard K&R C,[11] og i 1983 ble algoritmen omskrevet for Unix-avarten Berkeley Software Distribution.[11] Algoritmen ble i 1973 implementert i C-standardbiblioteket i form av funksjonen qsort,[12] og i 1989 ble den standard i ANSI C/C90. Funksjonen er også en del av referanseimplementasjonen av Java.[12]

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.[13] 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[14] så vel som derivasjoner av forventede antall sammenligninger og bytter.[11] 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.[11] 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.[15] 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(n2) når alle elementene er identiske.[16]

I 2009 foreslo den russiske informatikeren Vladimir Jaroslavskij en ny dobbel «dreietapp»-implementasjon av quicksort.[7] 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.[17] Hans versjon av quicksort ble i 2011 valgt som standard sorteringsalgoritme i versjon 7 av Oracle Corporations runtimebibliotek for Java etter omfattende empiriske ytelsestester.[12]

Algoritme

[rediger | rediger kilde]
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

[rediger | rediger kilde]

Denne metoden tilegnes Nico Lomuto og ble popularisert av Bentley i boken Programming Pearls,[18] og av Thomas H. Cormen med flere i boken Introduction to Algorithms.[19] 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.[20] I verste tilfelle krever denne metoden O(n2) sammenligninger. Det skjer når tabellen allerede er sortert eller når den bare har identiske elementer.[16] 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:[21] 

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

[rediger | rediger kilde]
Animasjon av Lomuto's metode
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.[22] 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.[16] Hoares partisjonering vil, liksom Lomuto's metode, kreve O(n2) 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:[21] 

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

[rediger | rediger kilde]

Jaroslavskijs metode benytter to «dreietapper».[7] Den partisjonerer den usorterte tabellen T [] a, hvor T er en primitiv type (heltall, flyttall, byte, tegn, dobbel, langt heltall og kort heltall) som defineres av to «dreietapper» P1 og P2. Det er derfor tre pekere, L, K, G, og to indekser, left and right, som peker på henholdsvis det første og det siste elementet.[7] Algoritmen består av følgende trinn:[7]

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

  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);
  }
  }

Ulike former for implementasjon

[rediger | rediger kilde]

Valg av «dreietapp»

[rediger | rediger kilde]

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.[23][24] 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 n er

{{{1}}}.

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

Cn, 2 ≈ 1.188 n log n

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

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 (lo hi)/2 forårsake overflyt og gi en feilaktig «dreietapp»-indeks. Dette kan bli unngått ved å bruke, for eksempel, 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

[rediger | rediger kilde]

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»,[11] 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).[11] 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.

Optimaliseringer

[rediger | rediger kilde]

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:[25]

  • For å være sikker på at for det meste 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å O(kn) for å avslutte sorteringen, en tid som er lineær hvis k er en konstant.[24][26] Sammenlignet med mange «småsorterings»-optimaliseringer, kan denne versjonen utføre færre instruksjoner, men den gjør ikke optimal bruk av hurtigminnet i moderne datamaskiner.[27]

Parallellisering

[rediger | rediger kilde]

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.[28][29] 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.[30] 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.[31]

Formell analyse

[rediger | rediger kilde]

Analyse av verste tilfelle

[rediger | rediger kilde]

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

[rediger | rediger kilde]

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 log2 n nøstede kall før vi kommer til en liste av størrelse 1. Dette betyr at dybden av kallstakken er log2 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

[rediger | rediger kilde]

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
[rediger | rediger kilde]

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.

Bruk av recurrency
[rediger | rediger kilde]
Denne seksjonen er en spire. Du kan bidra med å utvide den.

Se også

[rediger | rediger kilde]

Referanser

[rediger | rediger kilde]
  1. ^ Drange, Pål Grønås (27. januar 2023). «sorteringsalgoritme». Store norske leksikon (på norsk). Besøkt 3. mars 2023. 
  2. ^ «Algoritmer og datastrukturer - Kapittel 1   –   ». www.cs.hioa.no. Besøkt 3. mars 2023. 
  3. ^ «Algoritmer og datastrukturer - Kapittel 1». 
  4. ^ a b Computer History Museum 2017
  5. ^ a b Hoare 1961
  6. ^ Skiena 2008, side 129
  7. ^ a b c d e f g Jaroslavskij 2009
  8. ^ Shustek 2009
  9. ^ DeBarros 2015
  10. ^ Bell 1972
  11. ^ a b c d e f g h Bentley 1993
  12. ^ a b c Wild 2013
  13. ^ Sedgewick 1980
  14. ^ van Emden 1970
  15. ^ Oram 2007
  16. ^ a b c Computer Science 2017
  17. ^ Hacker News 1999
  18. ^ Bentley 1999
  19. ^ Cormen 2009
  20. ^ Wild 2012
  21. ^ a b Cormen 2009, side 170-190
  22. ^ Hoare 1962
  23. ^ Sedgewick 1998
  24. ^ a b Sedgewick 1978
  25. ^ GNU C 2017
  26. ^ Bentley 1999, side 117
  27. ^ LaMarca 1999
  28. ^ Acar 2013
  29. ^ Breshears 2012
  30. ^ Miller 2000
  31. ^ Powers 1991

Litteratur

[rediger | rediger kilde]
Hentet fra «https://no.wikipedia.org/w/index.php?title=Kvikksortering&oldid=23819065»