snabbsortering

Snabbsortering, eller quicksort på engelska, är en jämförande sorteringsalgoritm som utvecklades av Tony Hoare 1960. Den är en divide-and-conquer-algoritm som vanligtvis används som en in-place-sortering och har mycket god genomsnittlig prestanda.

Algoritmen väljer en pivot (en valfri samlingselement) och partitionerar arrayen i två delar: element som är mindre än pivoten och element som är större än pivoten. Sedan tillämpas sortering rekursivt på de två delarna.

Genomsnittlig tidskomplexitet är O(n log n). I värsta fall kan det bli O(n^2) om pivoten ofta är extremt dålig; detta motverkas vanligtvis genom slumpmässigt urval av pivoten eller metoder som median-of-three. Minne: i den klassiska in-place-varianten krävs O(log n) extra stackutrymme i genomsnitt.

Vanliga partitioneringsscheman är Hoare och Lomuto. Det finns även tre-vägs-partitionering för att hantera många lika element. Snabbsortering är vanligtvis inte stabil; stabila varianter finns men är mindre vanliga. Används ofta i standardbibliotek på många språk på grund av snabb genomsnittlig prestanda och god cache-beteende.

Se även mergesort, heapsort och stabil sortering.