Rangschikkingsalgoritmes

Rangschikkingsalgoritmes zijn algoritmes die een ongeordende verzameling elementen herordenen volgens een comparator, zodat de elementen in oplopende of aflopende volgorde komen te staan. Ze spelen een centrale rol in informatica en data-analyse.

Classificatie en eigenschappen: Rangschikkingsalgoritmes kunnen worden onderverdeeld in vergelijking-gebaseerde sorteringen en niet-vergelijken-sorteringen. Bij vergelijking-gebaseerde methoden wordt telkens een paar elementen vergeleken om een orde bepalen; niet-vergelijken-sorteringen maken gebruik van aannames over de input, zoals het bereik of de cijfers. Sorteren kan intern in het geheugen plaatsvinden of extern sorteren wanneer de dataset te groot is voor het geheugen.

Tijd- en ruimtecomplexiteit: Voor vergelijking-gebaseerde sorteringen geldt een bekende grens van Ω(n log n) vergelijkingen in het worst-case scenario, onder gangbare aannames. Niet-vergelijken-sorteringen kunnen sneller zijn bij specifieke aannames (bijvoorbeeld counting sort bij klein bereik). Stabiliteit en ruimtevereisten zijn belangrijke eigenschappen: stabiel betekent dat gelijke elementen hun oorspronkelijke volgorde behouden; in-place betekent dat weinig extra geheugen wordt gebruikt (vaak O(1) of O(log n)).

Voorbeelden van algoritmes:

- Eenvoudige sorteringen zoals bubble sort, insertion sort en selection sort, meestal O(n^2) in tijd.

- Merge sort: O(n log n) in alle gevallen, stabiel, maar vereist extra geheugen.

- Quicksort: O(n log n) gemiddeld, O(n^2) worst-case; meestal in-place maar niet stabiel.

- Heapsort: O(n log n), in-place, niet stabiel.

- Counting sort en radix sort: O(n + k) respectievelijk O(nk), stabiel en geschikt bij passende aannames.

- Bucket sort: afhankelijk van verdeling en bereik, kan zeer snel zijn.

Toepassingen omvatten sortering van records, databaseoperaties, preprocessing voor zoekalgoritmen en algemene data-analyse. Bij zeer grote datasets kan externe sortering nodig zijn.