Auswahlalgorithmus

Auswahlalgorithmen

Ein Auswahlalgorithmus bestimmt in einer Sammlung geordneter Werte den k-ten kleinsten Wert. Dieser Wert heißt Statistik k-ter Ordnungstatistik. Solche Algorithmen werden unter anderem genutzt, um Minimum, Median oder Maximum eines Datensatzes zu ermitteln.

Ein Beispiel ist Quickselect. Auswahlalgorithmen müssen nicht die gesamte Sammlung sortieren, sondern sollen gezielt das Element an der gesuchten Rangposition finden.

Zwei Problemvarianten

Es gibt zwei Varianten, je nachdem, ob gleiche Werte erlaubt sind.

Bei n unterschiedlichen Elementen, einer Ordnung und einer ganzen Zahl k ≤ n wird das Element gesucht, das strikt größer als genau k − 1 Elemente ist.

Bei n Elementen, bei denen gleiche Werte vorkommen können, wird ein Element gesucht, das größer als maximal k − 1 Elemente und zugleich kleiner als maximal n − k Elemente ist. Diese Bedingungen berücksichtigen, dass mehrere Elemente denselben Wert haben können.

Verfahren

Beide Problemvarianten können mit Sortierverfahren, Quickselect, dem Floyd-Rivest-Algorithmus, Median of Medians und Introselect gelöst werden. Diese Verfahren beruhen auf Vergleichen zwischen Elementen.

Radix Select arbeitet anders: Es vergleicht die Elemente nicht direkt, sondern ordnet sie nach ihren Werten in Buckets ein. Danach bestimmt es, welcher Bucket das gesuchte k-te kleinste Element enthält, und verarbeitet die Elemente dieses Buckets rekursiv weiter.

Bei Tests mit zufälligen Eingabewerten erzielte Radix Select in der Praxis eine hohe Performance im Vergleich zu Quickselect und Median of Medians.