selectiealgoritme

Selectiealgoritme is een type algoritme dat uit een ongesorteerde verzameling gegevens een element teruggeeft dat in de gesorteerde volgorde op een specifieke positie ligt, meestal de k-de orde-statistiek. Een veelvoorkomend voorbeeld is de mediaan, die bij een rij met n elementen de middelste waarde oplevert (k = floor((n+1)/2)).

Een algemene benadering is quickselect, gebaseerd op partitionering zoals bij Quicksort. Een pivot wordt gekozen, de rij wordt opgesplitst in elementen kleiner en groter dan de pivot, en de zoekruimte wordt gericht op de partitie die de gewenste positie bevat. Gemiddelde tijdscomplexiteit is O(n), met in-place implementaties die O(1) extra geheugen vereisen; in het slechtste geval kan de tijd O(n^2) oplopen.

Een deterministische lineaire tijd-algoritme is median-of-medians (Blum-Floyd-Pratt-Rivest-Tarjan). Het kiest een pivot via groepsgewijze selectie (vaak groepen van vijf) en reduceert daarmee in elke stap ten minste een constant deel van de elementen, zodat de totale tijd O(n) blijft in het worst-case.

Toepassingen en varianten: selectiealgoritmes worden gebruikt voor het berekenen van orde-statistieken zoals de mediaan, percentielen en kleinste/grootste elementen. Ze vormen ook bouwstenen in data-analyse, statistiek en databases. Er zijn meerdere implementatievarianten, met verschillende trade-offs tussen snelheid, geheugenverbruik en worst-case garanties.

Zie ook: orden-statistieken, quicksort, order-statistic tree.