Sorteercomplexiteit

Sorteercomplexiteit verwijst naar de hoeveelheid bronnen die nodig is om een verzameling elementen te sorteren, meestal tijd en geheugen. In algoritmetheorie wordt tijdcomplexiteit uitgedrukt met asymptotische notaties zoals O, Ω en Θ. De analyse hangt af van aannames over de invoer, zoals willekeur of een al gesorteerde beginvolgorde.

Tijdcomplexiteit kent worst-case, gemiddelde-case en best-case. Voor vergelijking-sorteringen geldt een ondergrens: in het slechtste geval vereisen algoritmen die uitsluitend sleutels vergelijken Ω(n log n) vergelijkingen. Dit vormt de basis voor de meeste sorteerontwerpen.

Belangrijke algoritmen: Quicksort heeft gemiddeld O(n log n) tijd maar kan O(n^2) worden in het slechtste geval zonder maatregelen. Mergesort garandeert O(n log n) en is meestal stabiel, maar vereist extra geheugen. Heapsort is O(n log n) en in-place. Niet-vergelijkings-sorteringen zoals Counting Sort en Radix Sort kunnen sneller zijn bij een beperkt sleutelbereik of veel identieke sleutels; hun complexiteit kan O(n) of O(nk) zijn, afhankelijk van de aannames.

Stabiliteit en ruimtegebruik beïnvloeden de keuze. Stabiliteit behoudt de volgorde van gelijke sleutels; mergesort is meestal stabiel, Counting Sort kan dit ook zijn. In-place-algoritmen gebruiken weinig extra geheugen, maar kunnen minder praktisch zijn. Voor zeer grote datasets is externe sortering relevant, waarbij sorteren buiten het hoofdgeheugen gebeurt.

Praktisch hangt de keuze af van data-eigenschappen en systeemlimieten: sleutelbereik, datasetgrootte, geheugen en mogelijk parallelle uitvoering. Moderne systemen combineren vaak technieken en optimalisaties om praktische prestaties te verhogen, terwijl de theoretische tijdcomplexiteiten als leidraad blijven gelden.