sorteermethode

Een sorteermethode is een algoritme dat een verzameling gegevens, zoals een lijst of array, herschikt zodat de elementen in een gewenste volgorde komen, meestal oplopend of aflopend op basis van een sleutel.

Sorteeralgoritmes worden onderverdeeld in twee hoofdklassen: vergelijking-gebaseerde sortering en niet-vergelijkende sortering. Bij vergelijking-gebaseerde sortering worden elementen uitsluitend bepaald door de uitkomsten van vergelijkingen; niet-vergelijkende methoden maken gebruik van kenmerken zoals cijfers of waarden. Daarnaast kan een sortering stabiel zijn (gelijke sleutels behouden de oorspronkelijke volgorde) en/of in-place (zonder of met beperkte extra ruimte).

De tijdscomplexiteit varieert sterk. Eenvoudige methoden zoals bubbel-, selectie- en invoegsorteren hebben vaak O(n^2) tijd in het slechtste of gemiddelde geval. Geavanceerde methoden zoals quicksort, mergesort en heapsort bereiken doorgaans O(n log n) tijd. Quicksort is meestal in-place maar niet stabiel; mergesort is stabiel en vereist doorgaans extra ruimte; heapsort is in-place en niet stabiel.

Veelgebruikte sorteermethoden zijn onder meer bubblesort, selectie-sortering en invoegsortering; ook snelle methoden zoals quicksort en mergesort komen veel voor; heapsort is een alternatief dat in-place werkt; en niet-vergelijkende methoden zoals counting sort of radix sort bestaan voor specifieke datasets.

De keuze voor een sorteermethode hangt af van factoren als datasetgrootte, geheugenlimieten, de wenselijkheid van stabiliteit en of de data al gedeeltelijk gesorteerd is. Voor grote datasets en geheugenbeperkingen zijn algoritmes met O(n log n) tijd en in-place werking vaak geschikt; voor kleine lijsten kunnen eenvoudige O(n^2) algoritmes in praktijk sneller blijken.