In der Informatik ist ein Auswahlalgorithmus ein Algorithmus zum Auffinden des -ten kleinsten Wertes in einer Sammlung von geordneten Werten. Der ermittelte Wert wird als Statistik -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 Es gibt mehrere Varianten des Problems. Einerseits wird in Cormen et al. angenommen, dass alle Elemente der Menge unterschiedlich sind, andererseits sind in Blum et al. gleiche Elemente vorgesehen.
Im ersten Fall ergibt sich die Problemstellung: Finden Sie bei einer Menge von unterschiedlichen Elementen, einer Ordnung dieser Elemente und einer ganzen Zahl , die kleiner gleich ist, das Element, das strikt größer als genau Elemente ist.
Im zweiten Fall ergibt sich die Problemstellung: Finden Sie bei einer Menge von Elementen, einer Ordnung dieser Elemente und einer ganzen Zahl k, die kleiner gleich ist, ein Element, das größer als maximal Elemente ist und gleichzeitig kleiner als maximal Elemente ist.
Algorithmen Algorithmen die in der Lage sind beide Varianten des Problems zu lösen sind Sortierverfahren, quickselect, Floyd-Rivest-Algorithmus, 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 -te kleinste Element befindet, und bearbeitet die Elemente im Bucket rekursiv weiter.
Im Test mit zufälligen Eingabewerten erreichte der Radix Select in der Praxis eine hohe Performance verglichen mit Quickselect und Median of Medians.
Einzelnachweise
Kategorie:Algorithmus Kategorie:Statistik