Quicksort

Från Rilpedia

Texten från svenska Wikipedia

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 (n²) 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 3 (ett från början ett från slutet och ett från mitten av listan).

Algoritmen

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 än 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

Här kommer en kodsnutt 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.