Quicksort

Animatie quicksort

Quicksort is een recursief sorteeralgoritme bedacht door Tony Hoare. Hij werkte destijds aan een project in verband met computervertalingen. Daarvoor was het nodig om korte Russische zinnen snel en efficiënt te sorteren. Het algemene werkingsprincipe van quicksort wordt weleens kort omschreven als verdeel en heers.

Werkingsprincipe

Het doel van quicksort is om een rij van ongesorteerde getallen, gesorteerd terug te geven. Dit gebeurt in 4 stappen.

1. Als de rij één of geen elementen bevat. STOP
2. Kies een willekeurig element in de rij. Dit element, blauw aangeduid in de figuur, wordt de spil of de pivot genoemd.
3. Herschik de rij zodat alle elementen met een waarde kleiner of gelijk aan die van de spil links van de spil belanden en alle elementen met een waarde groter dan die van de spil rechts van de spil belanden. Deze stap wordt het partitioneren genoemd.
4. Sorteer de linker en de rechter deelrij. (Door middel van quicksort.)

• 
  Voor partitioneren
• 
  Na partitioneren

Hierbij zijn de volgende zaken vermeldenswaardig. In stap 2 wordt een willekeurig element gekozen. Iedere keuze van de spil leidt tot een werkend algoritme. Het willekeurig kiezen van de spil leidt praktisch tot de beste resultaten, al geeft dit enkele theoretische nadelen. Zo is het moeilijk om het algoritme te analyseren. Bovendien voldoet een algoritme dat een willekeurige stap bevat niet aan de striktere definities van een algoritme. In stap 3 wordt niet gespecificeerd hoe deze stap uitgevoerd moet worden. Dit wisselt in verschillende implementaties. Het exacte verloop van deze stap wordt onder de kop partitionering besproken. In stap 4 roept het algoritme zichzelf op. Quicksort is dus een recursief algoritme.

Partitionering

Er zijn verschillende mogelijkheden om de rij te partitioneren. Hier wordt de methode van Nico Lomuto besproken.

Illustratie van de deelrijen

Om dit algoritme te begrijpen moet men inzien dat het met 3 volgende deelrijen werkt.

• De deelrij die kleinere of gelijke elementen bevat. Beslaat de posities [0,i-1]
• De deelrij die grotere elementen bevat. Beslaat [i,j-1]
• De deelrij die alle nog niet vergeleken elementen bevat. Beslaat [j,n-1]

Het basisidee van het algoritme is nu eenvoudig. Plaats eerst de spil op de laatste positie. Neem het eerste element uit de deelrij met nog niet vergeleken elementen en vergelijk het met de spil. Plaats dit element achter de deelrij waar het in moet komen. Pas vervolgens de grenzen van de deelrijen aan.

Een animatie van het lomuto algoritme

Het formele algoritme wordt nu

1. Plaats de spil achteraan de rij.
2. zolang j<n-1
   1. Als element op positie j kleiner of gelijk aan spil.
      1. Wissel i en j van plaats.
      2. Stel i=i+1
   2. Stel j=j+1;
3. Wissel element i en element j van plaats.

Na het uitvoeren van het algoritme staat de spil op plaats i en is de rij gepartitioneerd.

Hiernaast een grafische weergave.

Tijdscomplexiteit

Om de complexiteit van quicksort te berekenen redeneert men aan de hand van het aantal vergelijkingen. Het verwachte aantal benodigde vergelijkingen ligt in de orde O(n*log(n)). In de informatietheorie wordt bewezen dat $O(n*\log(n))$ hiervoor een ondergrens is. Merk op dat counting sort en radix sort sneller kunnen werken. Deze algoritmes hebben daarentegen wel nood aan informatie omtrent het bereik van de te sorteren waarden. Bovendien blijkt experimenteel dat quicksort slecht scoort met kleinere rijen.

Worstcasescenario

Wanneer het maximum of minimum (uit de niet gesorteerde deelrij) systematisch als spilelement wordt gekozen kan de prestatie van quicksort drastisch dalen. In dit geval zal de tijdscomplexiteit $O(n^{2})$ bedragen. De kans dat dit toevallig gebeurt is in het algemene geval enorm klein. Maar wanneer de rij gestructureerd is wordt deze kans toch reëel. Stel nu dat het algoritme zo geïmplementeerd is dat het altijd het eerste element in de rij als spil kiest. Wanneer dit programma een reeds gesorteerde lijst moet sorteren zal het systematisch het kleinste element als spil nemen. Om dit te vermijden kiest men in de praktijk de spil vaak willekeurig. Een andere oplossing bestaat erin om de mediaan van het eerste, het laatste en het middelste element te kiezen.

Weinig unieke waarden

Het tweede geval is het sorteren van een rij met weinig unieke waarden. Dit is bijvoorbeeld het geval wanneer men een lijst van personen op geslacht wilt sorteren. Het sorteeralgoritme quick-3 dat nauw verwant is aan quicksort lost dit probleem elegant op.

Bijna gesorteerde rij

Wanneer quicksort (met willekeurig gekozen spil) een bijna gesorteerde rij moet sorteren, zal het algoritme een tijdscomplexiteit van $O(n*\log(n))$ hebben. Dit is lager dan bij flexibele sorteeralgoritmes als insertion sort of bubblesort waarbij de tijdscomplexiteit $O(n^{2})$ bedraagt. Quicksort is dus geen flexibel algoritme.

Wanneer als spil echter het eerste of laatste element wordt gekozen, zal de complexiteit $O(n^{2})$ bedragen. Omdat (bijna) alle waarden steeds achter, respectievelijk voor de spil liggen, worden geen (indien volledig gesorteerd) of nagenoeg geen (indien bijna gesorteerd) deelrijen gemaakt en zal het algoritme suboptimaal werken.

Ruimtecomplexiteit

De ruimtecomplexiteit van quicksort bedraagt $O(\log(n))$. Dit kan men eenvoudig inzien. Er moeten immers log(n) functieoproepen worden opgeslagen. Merk op dat het opslaan van de rij O(n) niet in rekening wordt gebracht. Men verrekent enkel het extra gebruikte geheugen. Wanneer men voor een naïef partitioneringsalgoritme kiest, een dat de rij kopieert, dan zal de ruimtecomplexiteit O(n) bedragen.

Optimalisaties bij quicksort

Quick-3

Quicksort presteert slecht wanneer er weinig unieke waarden zijn. Het Quick-3-algoritme lost dit op een elegante manier op. Dit gebeurt door te partitioneren met 3 deelrijen in plaats van 2. Een deelrij die alle elementen met een kleinere waarde dan die van de spil bevat. Een deelrij die alle elementen met een waarde gelijk aan die van de spil bevat. En een deelrij die alle grotere waarden bevat. Men raadt dan ook aan om altijd quick-3 te gebruiken.

Kleine deelrijen

Het blijkt dat quicksort slecht scoort op kleine rijen. Daarom kiest men er soms voor om insertion sort te gebruiken voor kleine rijen. De waarde waarvoor dit moet gebeuren wordt dan experimenteel bepaald.

Enkel getallen

Indien men enkel getallen moet sorteren en wanneer meer geheugen gebruikt mag worden, kiest men beter voor Counting sort.

Algemeen gebruik

De gerandomiseerde quicksort behaalt ongeacht de invoer een tijdscomplexiteit van $O(n*log(n))$. Wat gelijk is aan de absolute ondergrens. Toch kunnen andere algoritmes in sommige gevallen deze grens verbreken. Hieruit besluiten we dat wanneer er geen informatie is over de te sorteren data, quicksort (of beter quick-3) een ideaal algoritme is. Dit blijkt dan ook uit het feit dat quicksort werd opgenomen in de standaardbibliotheken van C en C++.

Voorbeeld in C#

public void QuickSort(int[] Lijst)             
{
  Sort(Lijst, 0, Lijst.Length - 1);                // Tabel, Links en rechts meegeven
}/*QuickSort*/

private void Sort(int[] Lijst, int Links, int Rechts) 
{
  int L = Links;
  int R = Rechts;
  int middelsteElement = Lijst[(Links + Rechts) / 2];

  do 
  {
    while(Lijst[L] < middelsteElement) 
    {
      L++;
    }
    while(middelsteElement < Lijst[R]) 
    {
     R--;
    }

    if(L <= R) 
    {
      int linksteElement = Lijst[L];
      Lijst[L] = Lijst[R];
      Lijst[R] = linksteElement ;
      L++;
      R--;
    }
 } while(L < R);

  if(Links < R) 
  {
    Sort(Lijst, Links, R);
  }
  if(L < Rechts) 
  {
    Sort(Lijst, L, Rechts);
  }
}/*Sort*/

Voorbeeld in Scala

Een implementatie van het Quicksort-algoritme in Scala (illustratief omdat sortering ook in de Scala Standard Library-API kan worden aangeroepen):

// Sjabloon voor generieke sortering mits het sorteerbaar "[A <% Ordered[A]]" is
def quickSort[A <% Ordered[A]](xs: List[A]): List[A] = xs match {
  case Nil => xs                            // lege lijst, geef lege lijst terug
  case pivot :: lijst_zonder_kop =>         // ontbonden lijst met de fragmenten kop en staart
    lijst_zonder_kop partition (_ < pivot)  // splits de lijst in twee lijsten
    match { case (onder, boven) => quickSort(onder) ++ (pivot :: quickSort(boven)) }
}

Voorbeeld in Prolog

% Versie met recursie
qsort([],[]).
qsort([Spil|Rest],Sorted) :-
   split(Spil,Rest,Kleiner,Groter),
   qsort(Kleiner,KS),
   qsort(Groter,GS),
   append(KS,[Spil|Gs],Sorted).

% Versie met staartrecursie (een accumulerende parameter)
qsort(Lijst,Sorted) :- qsort(Lijst,[],Sorted).
qsort([],L,L).
qsort([Spil|R],Acc,Sorted) :-
   split(Spil,R,Kleiner,Groter],
   qsort(Groter,Acc,NewAcc),
   qsort(Kleiner,[Spil|NewAcc],Sorted).

split(Spil,[],[],[]).
split(Spil,[X|R],Kleiner,Groter) :-
   Spil > X, Kleiner = [X|RestK],
   split(Spil,R,RestK,Groter).
   split(Spil,[X|R],Kleiner,Groter) :-
   Spil =< X, Groter = [X|RestG],
   split(Spil,R,Kleiner,RestG).

Voorbeeld in Python3

def QuickSort(array, lowestVal,length):
  if lowestVal < length:
    q = partition(array, lowestVal, length)
    QuickSort(array, lowestVal, q-1)
    QuickSort(array, q+1, length)
  return array 

def partition(array, lowestVal, length):
  pivot = array[length]
  i = lowestVal - 1
  temp = 0
  for j in range(lowestVal, length):
    if array[j] <= pivot:
      i += 1
      temp = array[j]
      array[j] = array[i]
      array[i] = temp
  temp = array[i + 1]
  array[i + 1] = array[length]
  array[length] = temp
  return(i+1)