Quicksort

Wikipedia

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). Den använder sig av tekniken divide and conquer.

[redigera] 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.