Hybridsort ist ein spezielles Sortierverfahren, das die Eigenschaften von Bucketsort mit anderen Sortierverfahren wie Heapsort oder Quicksort kombiniert. Die zu sortierenden Schlüssel werden nach dem Prinzip von Bucketsort aufgeteilt. Die so vorsortierten Elemente werden dann mit dem Heapsort-Algorithmus endgültig sortiert. Die durchsortierten Kübel werden dann aneinandergefügt.
Voraussetzung Bearbeiten
Ähnlich wie bei Bucketsort muss die Anzahl der von den Sortierschlüsseln annehmbaren Werte endlich sein.
Prinzip Bearbeiten
Die Elemente einer Liste werden entsprechend ihrer Schlüsseleigenschaft auf eine endliche Menge von Eimern verteilt. Die Schlüssel werden mit Hilfe des maximalen Schlüssels auf das Intervall normiert. Durch die Anzahl der Körbe werden die Grenzen in diesem Intervall definiert. Mit folgender Formel werden dann die Elemente auf die Körbe verteilt:
Die so verteilten Schlüssel werden innerhalb der Körbe mit Heapsort sortiert.
Die vor- und durchsortierten Körbe liefern aneinandergereiht die sortierte Liste.
Komplexität Bearbeiten
Unter der Annahme, dass xi unabhängig und gleichverteilt ist ergibt sich sowohl im best als auch im average case des Verfahrens eine Laufzeit von auf. Für den allgemeinen Fall ergibt sich jedoch eine deutlich schlechtere Laufzeit. Der worst case wird dominiert von der Laufzeit von Heapsort und ist damit .
Literatur Bearbeiten
- Torben Hagerup: Hybridsort revisited and parallelized. In: Information Processing Letters. Band 32, Nr. 1, 1989, S. 35–39, doi:10.1016/0020-0190(89)90066-5.
- Henk Meijer und Selim G. Akl: The design and analysis of a new hybrid sorting algorithm. In: Information Processing Letters. Band 10, Nr. 4,5, 1980, S. 213–218, doi:10.1016/0020-0190(80)90143-X.