Hurtigsort

Hurtigsort er en generel sorteringsalgoritme baseret på del-og-hersk-princippet. Den sorterer en liste ved at vælge et pivot-element og opdele resten af elementerne i to grupper: dem mindre end pivot og dem større end pivot. De to dele sorteres rekursivt og sættes derefter sammen omkring pivotet til en samlet sorteret liste. I praksis sker dette ofte in-place, så kun lidt ekstra plads bruges, typisk stakken til rekursionen.

Den gennemsnitlige tidskompleksitet er O(n log n); værste tilfælde er O(n^2), hvilket kan forekomme hvis pivotet altid vælges som det mindst eller største element. For at mindske risikoen for worst-case anvendes ofte tilfældige pivots eller teknikker som median-of-three; moderne varianter som introsort kombinerer hurtigsort med heapsort for at sikre O(n log n) i værste fald.

Partitioneringsmetoderne Hoare og Lomuto er to velkendte til hurtigsort. Hoare-partitioneren flytter elementer rundt i forhold til pivotet og kan være mere effektiv i praksis, mens Lomuto er lettere at implementere men ofte lidt mindre effektiv.

Stabilitet er ikke en egenskab ved standard hurtigsort; den er som udgangspunkt ikke stabil. Der findes stabile varianter, men disse kræver ofte ekstra hukommelse eller mere komplekse partitioneringsregler.

Hurtigsort anvendes bredt som grundlæggende sortering i mange programmeringssprog og biblioteker på grund af sin generelle ydeevne og evne til at sortere store datamængder effektivt. Som en del af hybride løsninger bruges den ofte i praksis sammen med andre metoder for at sikre stabil ydeevne på forskellige datasæt.