sorteringsalgoritme

Sorteringsalgoritmer er metoder for å organisere en samling elementer i stigende eller synkende rekkefølge etter en sammenligningsfunksjon. De brukes i grunnleggende dataorganisering og som forberedelse for andre prosesser som søk og indeksering.

Algoritmene varierer i effektivitet, minnebruk og egenskaper som stabilitet og om sorteringen skjer in-place eller krever ekstra plass. De deles ofte inn i to hovedgrupper: sammenligningsbaserte sorteringer, som baserer seg på å sammenligne par av elementer, og ikke-sammenligningsbaserte sorteringer, som utnytter kjente verdier og kan ha spesielle tidsgrenser for spesifikke data. Sammenligningsbaserte metoder har vanligvis tidskompleksitet rundt O(n log n) i gjennomsnitt, selv om enkelte varianter kan falle til O(n^2) i verste fall. Ikke-sammenligningsbaserte metoder kan være raskere når verdier er begrensede eller har et kjent område, med passende kompleksiteter som ofte kan være O(n + k), avhengig av kontekst og implementasjon.

Vanlige eksempler inkluderer innsettingssortering (innsettingssortering), som er stabil og in-place men har O(n^2) verste fall; boblesortering (stabil, in-place, O(n^2)); utvelgingssortering (in-place, vanligvis O(n^2) og ofte ustabil); rask sortering (quicksort, O(n log n) i gjennomsnitt, O(n^2) i verste fall); flettesortering (mergesort, stabil og O(n log n), krever ofte ekstra plass); og heapsort (in-place, O(n log n), ikke-stabil). Avanserte varianter som TimSort og IntroSort brukes bredt i praksis for å hente ut bestefallene til ulike data.