Auswahlalgorithmus

In der Informatik ist ein Auswahlalgorithmus ein Algorithmus zum Auffinden des k-ten kleinsten Wertes in einer Sammlung von geordneten Werten. Der ermittelte Wert wird als Statistik k-ter Ordnungstatistik bezeichnet. Dies findet Anwendung bei der Ermittlung des Minimums, des Medians und des Maximums eines Datensatzes. Ein Beispiel für einen Auswahlalgorithmus ist quickselect.

Problemstellung

Das Problem lautet: Finden Sie bei einer Menge von n Objekten, einer Ordnung dieser Objekte und einer ganzen Zahl k, die kleiner als n ist, das Objekt, das strikt größer als genau k Objekte ist.