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 Minimum, des Median und des Maximums eines Datensatzes. Ein Beispiel für einen Auswahlalgorithmus ist quickselect.

Es gibt mehrere Varianten des Problems. Einerseits wird in Cormen et al.^[1] angenommen, dass alle Elemente der Menge unterschiedlich sind, andererseits sind in Blum et al.^[2] gleiche Elemente vorgesehen.

Im ersten Fall ergibt sich die Problemstellung: Finden Sie bei einer Menge von n unterschiedlichen Elementen, einer Ordnung dieser Elemente und einer ganzen Zahl k, die kleiner gleich n ist, das Element, das strikt größer als genau k - 1 Elemente ist.

Im zweiten Fall ergibt sich die Problemstellung: Finden Sie bei einer Menge von n Elementen, einer Ordnung dieser Elemente und einer ganzen Zahl k, die kleiner gleich n ist, ein Element, das größer als maximal k - 1 Elemente ist und gleichzeitig kleiner als maximal n - k Elemente ist.

Algorithmen die in der Lage sind beide Varianten des Problems zu lösen sind Sortierverfahren, quickselect, Floyd-Rivest-Algorithmus^[3], Median of Medians, Introselect.

Die zuvor genannten Algorithmen basieren auf Vergleichen zwischen Elementen. Der Algorithmus Radix Select vergleicht Elemente nicht miteinander, sondern sortiert die Elemente entsprechend ihren Werten in sog. Buckets ein. Anschließend berechnet der Algorithmus, in welchem der Buckets sich das gesuchte k-te kleinste Element befindet, und bearbeitet die Elemente im Bucket rekursiv weiter.^[4]

Im Test mit zufälligen Eingabewerten erreichte der Radix Select in der Praxis eine hohe Performance verglichen mit Quickselect und Median of Medians.^[5]

1. ↑ Thomas H. Cormen, Charles Eric Leiserson, Ronald Linn Rivest, Clifford Stein: Introduction to algorithms. Fourth edition Auflage. The MIT Press, Cambridge, Massachusetts London, England 2022 (englisch). 
2. ↑ Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, Robert E. Tarjan: Time Bounds for Selection. In: Journal of Computer and System Sciences. Band 7, Nr. 4, 1973, S. 448–461, doi:10.1016/S0022-0000(73)80033-9 (englisch). 
3. ↑ Robert W. Floyd, Ronald L. Rivest: Expected time bounds for selection. In: Communications of the ACM. Band 18, Nr. 3, 1975, S. 165–172, doi:10.1145/360680.360691 (englisch). 
4. ↑ Tolu Alabi, Jeffrey D. Blanchard, Bradley Gordon, Russel Steinbach: Fast K-selection Algorithms for Graphics Processing Units. In: ACM Journal of Experimental Algorithmics. 17. Jahrgang, Juli 2012, doi:10.1145/2133803.2345676 (englisch, blanchard.math.grinnell.edu (Memento des Originals vom 16. November 2025 im Internet Archive)). 
5. ↑ Radix Selection Algorithm. In: Algorithm Performance. 20. Oktober 2025, abgerufen am 29. Juli 2026 (englisch).