Hybridsort

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

Ähnlich wie bei Bucketsort muss die Anzahl der von den Sortierschlüsseln annehmbaren Werte endlich sein.

Prinzip

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 ${\text{max}}$ auf das Intervall $[0;1]$ normiert. Durch die Anzahl der Körbe $a$ werden die Grenzen in diesem Intervall definiert. Mit folgender Formel werden dann die Elemente auf die Körbe verteilt:

${\text{Index}}_{\text{Korb}}={\frac {\text{Schlüssel}}{\text{max}}}\cdot a$

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

Unter der Annahme, dass x_i unabhängig und gleichverteilt ist ergibt sich sowohl im best als auch im average case des Verfahrens eine Laufzeit von ${\mathcal {O}}(n)$ 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 ${\mathcal {O}}(n\cdot \log n)$.

Literatur

• 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.