sorteringsmetode

Sorteringsmetoder är en familj av algoritmer som syftar till att ordna en samling objekt i en definierad ordning, vanligen stigande eller fallande. De kan sortera olika typer av data, såsom tal, textsträngar eller sammansatta nycklar, och används i databearbetning, sökningar och många algoritmiska konstruktioner.

Delar: jämförande sortering och icke-jämförande sortering. Jämförande sortering bygger på att jämföra par av objekt och använda en total ordning. Den teoretiska nedre gränsen för tid är O(n log n) för allmänna fall, med vissa specialfall undantagna. Icke-jämförande sortering utnyttjar kända nyckelområden och kan ibland uppnå O(n) tid, exempelvis CountingSort eller RadixSort under gynnsamma antaganden.

Vanliga algoritmer: Snabb sortering (Quicksort) har i genomsnitt O(n log n) tid, är vanligtvis in-place men blir inte alltid stabil; mergesort uppnår O(n log n), är stabil och ofta kräver extra minne; heapsort är O(n log n), in-place men inte stabil; InsertionSort och BubbleSort är enkla men ofta O(n^2) i värsta fall, bra för små eller nästan sorterade data.

Jämfört med stabilitet och minnesanvändning: stabila sorter bevarar lika nycklar relativa ordning; in-place sorter kräver liten eller ingen extra minne.

Val av metod beror på dataegenskaper och krav: storlek, nyckelområde, om ordningen mellan lika nycklar måste bevaras, och om algoritmen ska vara enkel att implementera eller lätt att parallellisera. I praktiken används ofta hybrider eller delar av såväl som Timsort i programmeringsspråk som Java och Python.