Quicksort

Från Wikipedia
Hoppa till: navigering, sök
Animation som visar Quicksort-algoritmen över ett antal osorterade staplar. De röda staplarna markerar pivot-element; vid animationens början väljs elementet längst till höger som pivot.

Quicksort är en av de snabbaste sorteringsalgoritmerna. Den sorterar n objekt med tidskomplexitet O (n2) i värsta fall och med en genomsnittlig tidskomplexitet O (n log n). En förutsättning för att man når denna komplexitet är att man väljer rätt pivot-element, ett slumpvist valt är bra men man brukar nöja sig med medianen av tre (ett från början ett från slutet och ett från mitten av listan).

Algoritmen[redigera | redigera wikitext]

Quicksortalgoritmen är av typen söndra och härska, och har följande steg

  1. Välj ett element, kallat pivotelement, ur listan
  2. Ordna om listan så att alla element som är mindre eller lika med pivotelementet kommer före detta, och så att alla element som är större än pivotelementet kommer efter detta. Pivotelementet har nu fått sin rätta plats.
  3. Sortera rekursivt de två dellistorna, dvs. med just denna algoritm.

Basfallet för rekursionen är en lista med ett element (i vissa implementationer används en tom lista som basfall).

Exempel[redigera | redigera wikitext]

Här kommer exempelkod i Haskell som beskriver vad som händer;

 sort []           = []
 sort (pivot:rest) = 
                     sort [y | y <- rest, y < pivot] 
                     ++ [pivot] ++ 
                     sort [y | y <- rest, y >=pivot]

Blir: "små element" + pivot + "stora element" Notera att vi väljer det första elementet i listan som pivot-element vilket kan leda till fruktansvärt dålig prestanda om listan från början är (nästan) sorterad eller inverterat sorterad.