Quicksort – effektiv partitionerande sorteringsalgoritm (Hoare, 1959)

Quicksort – snabb partitionerande sortering av Tony Hoare (1959). Förklarar partitionering, jämförelser, komplexitet och praktiska optimeringar för effektiv sortering.

Quicksort är en sorteringsalgoritm som används för att sortera element i ett fält (array). Den skapades av Tony Hoare 1959 och används fortfarande flitigt idag. Quicksort fungerar genom att dela upp fältet i mindre delar—så kallade partitioner—och sorterar dessa rekursivt. Algoritmen är jämförelsebaserad: den väljer ett element som pivot, jämför övriga element med pivotelementet och placerar mindre element på ena sidan och större på andra sidan. Genom upprepade uppdelningar blir hela fältet sorterat.

Hur det fungerar (översikt)

Grundidéerna i Quicksort kan beskrivas i följande steg:

• Välj ett pivotelement (t.ex. första, sista, slumpmässigt eller median‑av‑tre).
• Partitionera fältet så att element mindre än pivot hamnar på ena sidan och element större än pivot på andra.
• Anropa Quicksort rekursivt på de två partitionerna.
• När partitionerna är små (t.ex. ett eller noll element) är de redan sorterade.

Partitioneringsscheman

Det finns flera sätt att partitionera. De två vanligaste är:

• Hoares partitioneringsschema (den ursprungliga metoden): använder två pekare som rör sig mot varandra från båda ändarna och byter element som står på fel sida av pivot. När pekarna möts eller korsar varandra är partitioneringen klar. Detta schema är ofta snabbare i praktiken och gör färre byten.
• Lomuto‑schemat: använder en enkel genomgång med en "storeIndex" och gör fler byten men enklare att implementera och förstå. Lomuto är känsligare för vissa dåliga pivotval.

Prestanda och komplexitet

• Genomsnittlig tid: O(n log n) — det här är varför Quicksort ofta är mycket snabb i praktiken.
• Bästa fall: O(n log n) — sker om partitionerna blir jämt delade.
• Värsta fall: O(n²) — inträffar om partitionen alltid blir extrem (t.ex. redan sorterat fält och pivot väljs som första eller sista element utan försiktighet).
• Extra minne: O(log n) i genomsnitt för rekursionsstacken (in‑place sortering); i värsta fall O(n) om rekursion blir maximal.
• Stabilitet: Quicksort är i allmänhet inte stabil (lika element kan ändra relativ ordning).

Praktiska förbättringar

• Slumpmässig pivot: välj pivot slumpmässigt för att undvika det typiska värsta fallet på vissa indata.
• Median‑av‑tre: välj pivot som medianen av första, mittersta och sista elementet för att få bättre delning i många praktiska fall.
• Byte till insertion sort: för små partitioner (t.ex. storlek < 10) är insertion sort ofta snabbare; många implementationer byter metod för små subproblem.
• Tail‑rekursion och iterativa varianter: minskar stackdjup genom att alltid rekursivt anropa den mindre partitionen och iterera över den större.

Varför används Quicksort ofta?

• Mycket snabb i praktiken tack vare få jämförelser och god cache‑lokalitet.
• Kan implementeras in‑place utan behov av temporära fält (till skillnad från exempelvis mergesort).
• Flexibel: många enkla förbättringar (randomisering, median‑av‑tre, hybridlösningar) gör att den fungerar bra på varierande data.

Jämförelse med andra algoritmer

Jämfört med mergesort har Quicksort bättre genomsnittlig prestanda och använder mindre extra minne, men mergesort har garanterad O(n log n) i alla fall och är stabil (om implementerad så). Heapsort ger också O(n log n) i alla fall och är in‑place men brukar vara långsammare i praktiken på grund av fler jämförelser och sämre cache‑prestanda.

Egenskaper (kort)

• Typ: jämförelsebaserad, partitionerande
• Stabil: nej
• In‑place: vanligtvis ja (med rekursionsstack)
• Tid: bästa/medel/värsta — O(n log n) / O(n log n) / O(n²)

Sammanfattningsvis är Quicksort en enkel, snabb och praktiskt användbar algoritm för sortering. Genom att välja pivotelement klokt och kombinera med andra optimeringar kan man få mycket goda resultat i praktiska program.

Sök med bokstav