Quicksort

Van Wikipedia

Quicksort voorbeeld

Quicksort is een sorteer-algoritme uitgevonden door Tony Hoare.

Inhoud

1 De basis
2 Van kleurenprobleem naar Quicksort
3 Programmavoorbeeld
4 Efficiëntie van Quicksort

[bewerk] De basis

QuickSort sorteert op basis van recursie en omwisseling. In een set gegevens van N elementen wordt ergens een spilwaarde gekozen (meestal gewoon de middelste). Dan wordt van de onderkant van de set gezocht naar een waarde die groter is dan de spil, en van de bovenkant naar een waarde die kleiner is dan de spil. Deze worden omgewisseld, en dit wordt herhaald tot de zoekpointers tot aan de spil komen. Dan zijn alle gegevens aan de ene kant kleiner dan de spil, en aan de andere kant groter. Door nu de QuickSort over deze twee deel-sets aan te roepen (recursie), worden deze ook weer voor-gesorteerd, net zolang tot de deelset nog maar uit 1 data-element bestaat, en de hele set gesorteerd is.

Quicksort is een veralgemenisering van het twee kleuren of het drie kleuren probleem (dit laatste probleem wordt ook wel het Nederlandse Vlag probleem genoemd).

In deze problemen gaat het erom een verzameling van elementen te ordenen. Ieder element heeft een kleur (rood en blauw of anders rood, wit en blauw). De elementen met de verschillende kleuren zitten door elkaar gehusseld in een rij. De bedoeling is nu de elementen in de rij zo te ordenen dat alle blauwe elementen in het linker gedeelte van de rij komen te liggen en alle rode in het rechter gedeelte. In de driekleuren-variant komt wit in het midden terecht, waarmee de Nederlandse vlag gevormd wordt.

Uiteraard is het niet mogelijk om de rij in een stap te ordenen. Een dergelijke, grote operatie valt niet te overzien. Het is daarom nodig dit ordenen te doen in een groter aantal simpele stappen, waarbij in iedere stap niet meer dan twee elementen van plaats verwisseld worden. Dit idee kunnen we formaliseren (we illustreren dit aan de hand van de twee-kleuren variant):

Om te beginnen hebben we een rij van gehusselde elementen; deze rij van N elementen noemen we r -- de elementen nummeren we vanaf 0:

r : rij[0..N) van {blauw, rood}

Vervolgens delen we de rij op in drie stukken: het blauwe stuk, het rode stuk en het ongeordende stuk in het midden. Deze stukken geven we aan door de grensposities, de plaatsen waar een stuk overgaat in een ander. Deze grensposities slaan we op, waarmee we meteen twee invarianten van het programma hebben dat dit probleem oplost.

b : [0..N]; {INV0: $\forall_{i, 0 \leq i < b} : (r.i = blauw)$ , oftewel alle elementen links van positie b zijn blauw)

t : [0..N]; {INV1: $\forall_{i, t \leq i < N} : (r.i = rood)$ , oftewel alle elementen rechts van positie t-1 zijn rood)

Als we nu voor b de waarde 0 kiezen en voor t de waarde N, dan zijn de rode en blauwe stukken precies leeg -- dit past bij de beginsituatie, waarin de rij geheel bestaat uit het ongeordende stuk. Verder geldt dat de rij geheel geordend is (het ongeordende stuk is leeg) als b = t.

Alleen, hoe moeten we de rij nu zover krijgen dat b = t? Dit kan door de rij element voor element te ordenen, te beginnen vanaf positie t-1 (of vanaf positie b, maar t-1 is traditioneler). We kunnen namelijk beredeneren wat er allemaal kan als we kijken naar positie t-1:

Stel, r.(t-1) is rood. Dit geeft geen aanleiding om iets met b te doen, maar we kunnen nu wel t straffeloos met 1 verlagen. Immers,

$\begin{matrix} & INV1(t := t - 1) \\ \equiv & \{\mbox{substitutie}\} \\ & \forall_{i, t - 1 \leq i < N} : (r.i = rood) \\ \equiv & \{\mbox{splits af het geval i = t - 1}\} \\ & r.(t-1) = rood \wedge \forall_{i, t \leq i < N} : (r.i = rood) \\ \equiv & \{\mbox{INV1 wisten we al}\} \\ & r.(t-1) = rood \\ \equiv & \{\mbox{daar gingen we nou juist van uit}\} \\ & true \end{matrix}$

Stel, r.(t-1) is blauw. Dit geeft geen aanleiding om iets met t te doen, maar we kunnen wel b met 1 verhogen als we dit element (waarvan we zeker weten dat het blauw is) op positie b zetten. Immers,

$\begin{matrix} & INV0(b := b + 1) \\ \equiv & \{\mbox{substitutie}\} \\ & \forall_{i, 0 \leq i < b + 1} : (r.i = blauw) \\ \equiv & \{\mbox{splits af het geval i = b}\} \\ & r.b = blauw \wedge \forall_{i, 0 \leq i < b} : (r.i = blauw) \\ \equiv & \{\mbox{INV0 wisten we al}\} \\ & r.b = blauw \end{matrix}$

En dat laatste kunnen we zeker voor elkaar krijgen als we het element op positie b omwisselen met het element op positie t-1, waarvan we weten dat het blauw is. Merk op dat we hiermee zeker niet INV1 verpesten -- INV1 gaat over de elementen t t/m N-1 en element t-1 valt daar buiten.

Door deze analyse kunnen we makkelijk inzien dat het volgende programmaatje het probleem oplost:

 r : rij[0..N) of {blauw, rood}; {r is geinitialiseerd}
 b, t : [0,N];
    
 |[ b, t := 0, N; {INV0 en INV1 gelden vanaf hier}
    
    do b < t ->
      {INV0, INV1 en b < t}
      if r.(t-1) = rood -> {INV0, INV1 en r.(t-1) = rood} t := t - 1
      [] r.(t-1) = blauw ->  {INV0, INV1 en r.(t-1) = blauw} 
                             r.b, r.(t-1) := r.(t-1), r.b
                            ;{INV0, INV1 en r.b = blauw}
                             b := b + 1
      fi
      {INV0, INV1}
    od 
    {INV0, INV1 en t = b, dus r is geordend}
 ]|

Vanuit het tweekleuren probleem is het niet moeilijk te bedenken dat een dergelijk algoritme ook een rij getallen kan ordenen ten opzichte van een waarde (namelijk kleiner-dan-of-gelijk-aan en groter-dan). Deze variatie op het bovenstaande programma ziet er wellicht als volgt uit -- merk op dat als vergelijkingswaarde de waarde op de eerste positie in de originele rij wordt genomen:

 r : rij[0..N) of integer; {r is geinitialiseerd}
 b, t : [0,N];
 kantelpunt : integer;
    
 |[ kantelpunt := r.0;
    b, t := 0, N; 
    
    do b < t ->
      if r.(t-1) > kantelpunt -> t := t - 1
      [] r.(t-1) <= kantelpunt ->  r.b, r.(t-1) := r.(t-1), r.b
                                  ;b := b + 1
      fi
    od 
 ]|

[bewerk] Van kleurenprobleem naar Quicksort

Het doel van Quicksort is om een rij waarden te ordenen naar grootte. Hierboven hebben we een algoritme gepresenteerd dat een rij kan ordenen ten opzichte van een kantelpunt. Is het mogelijk om van hieruit een algoritme te ontwikkelen dat de rij geheel ordent?

Dat is inderdaad mogelijk. Na afloop van het bovenstaande programma is de rij geordend ten opzichte van het kantelpunt: het rechter gedeelte van de rij is geheel groter, het linker gedeelte in zijn geheel ten hoogste het kantelpunt. Stel dat we uit deze beide stukken een nieuw kantelpunt kiezen en op de beide delen afzonderlijk dit algoritme herhalen -- dan hebben we opeens een rij in vier kleinere delen die ten opzichte van elkaar geordend zijn. Het vergt weinig fantasie om in te zien dat we deze truuk kunnen blijven herhalen totdat we de rij hebben onderverdeeld in N deelrijen, allemaal ter lengte 1, allemaal geordend ten opzichte van elkaar. Op dit moment is dan ook de hele rij geordend. Het geheel ziet er als volgt uit:

 r : rij[0..N) of integer; {r is geinitialiseerd}
 Quicksort(0, N);
    
       
 Quicksort = Procedure(links, rechts : integer) = 
 |[ b, t, kantelpunt : integer;
    |
    if rechts - links < 1 -> verlaat procedure fi; {Verder gaan heeft geen zin}
   
    kantelpunt := r.links;
    b, t := links, rechts; 
    
    do b < t ->
      if r.(t-1) > kantelpunt -> t := t - 1
      [] r.(t-1) <= kantelpunt ->  r.b, r.(t-1) := r.(t-1), r.b
                                  ;b := b + 1
      fi
    od 
   ;Quicksort(links, b)
   ;Quicksort(t, rechts)
 ]|

Merk op dat het Quicksort-programma zichzelf aanroept om de rij te ordenen; Quicksort is een voorbeeld van een recursief algoritme.

[bewerk] Programmavoorbeeld

Hier volgt een voorbeeld in C. De functie quicksort sorteert de array "data" met "lengte" aantal elementen volgens het quicksort algoritme. Het eerste element wordt als kantelpunt gekozen.

 //quicksort sorteert de array "data" met "lengte" aantal elementen
 void quicksort(int data[],int lengte){
   int i;
   int resultaat[lengte];
   int kleiner=0,groter=lengte-1;
   
   if(lengte>1){ //als er geen of 1 element is, dan moet er niet gesorteerd worden
     //neem als pivot het eerste element
     for(i=1;i<lengte;i++){ //ga al de andere elementen af
       if(data[i]<data[0]){ //kleiner dan pivot, plaats vooraan in resultaat
         resultaat[kleiner]=data[i];
         kleiner++;
       }else{ //groter als pivot, plaats achteraan in resultaat
         resultaat[groter]=data[i];
         groter--;
       }
     }
     resultaat[kleiner]=data[0]; //zet het pivot juist
     for(i=0;i<lengte;i++) data[i]=resultaat[i]; //kopieer resultaat naar data
     if(lengte>2){//als er minder dan 3 elementen zijn, dan zijn ze daarjuist gesorteerd
       quicksort(data,kleiner); //sorteer groep voor pivot
       quicksort(data+kleiner+1,lengte-kleiner-1); //sorteer groep na pivot
     }
   }
 }

[bewerk] Efficiëntie van Quicksort

Het grote voordeel van het quicksort-algoritme is dat het van alle algemene sorteeralgoritmen de beste tijdscomplexiteit heeft: de verwachte tijdscomplexiteit ligt in de orde O(n*log(n)). Dat wil zeggen dat quicksort een rij van n elementen ordent in ongeveer n * log(n) stappen.

Quicksort heeft echter ook enkele niet te verwaarlozen nadelen. Allereerst zit er een ergste-geval valkuil in het algoritme; afhankelijk van hoe het algoritme geïmplementeerd is zal het algoritme ofwel als de sorteren lijst al gesorteerd is, ofwel als de te sorteren lijst omgekeerd gesorteerd is een tijdscomplexiteit van O(n*n) hebben. Dit maakt het Quicksort algoritme veelal onbruikbaar in situaties waarbij een tijdige voltooiing gegarandeerd moet worden, ongeacht wat er gesorteerd moet worden. Dit kan bijvoorbeeld het geval zijn bij websites, als de website iets sorteert dat de gebruiker opstuurt, dan mag het niet zo zijn dat een kwaadwillend persoon door het lijstje in de juiste volgorde aan te bieden de server kan overbelasten.

Een ander nadeel is dat het Quicksort algoritme (gemiddeld) weliswaar O(n*log(n)) is, maar dit geldt in de orde van het aantal vergelijkingen. Dit is in de meeste gevallen juist, maar veel gevallen, bijvoorbeeld als getallen gesorteerd worden, is het vergelijken van twee waarden niet de meest tijdrovende operatie in het algoritme. In zo'n geval begint de tijd die de recursie kost te tellen en zal Quicksort het vaak verliezen van bijvoorbeeld Shellsort, welke niet recursief is.

Het laatste nadeel is dat het algoritme minder geschikt is om kleine hoeveelheden data (in de orde van 20 elementen of zoiets) te sorteren, het is (relatief) veel programmacode en veroorzaakt een grotere aanslag op de cache geheugens (stackgebruik recursie) en branchvoorspellingstabellen (meer voorwaardelijke sprongen) van moderne processoren.

In het algemeen blijkt Quicksort echter een ideaal algoritme en is het voor veel programmeurs de eerste keus. Ongetwijfeld heeft de opname van Quicksort in de standaardbibliotheek van de programmeertalen C en C++ hiertoe veel bijgedragen -- dat, en ook de aansprekende naam van het algoritme.

Categorie: Sorteeralgoritme