2001:9E8:B326:F000:3943:7460:6659:8E95: /* Komplexität */

2024-08-11T14:40:01Z

Komplexität

Neue Seite

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

:<math>\text{Index}_\text{Korb} = \frac{\text{Schlüssel}}{\text{max}} \cdot a</math>

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''<sub>i</sub> unabhängig und gleichverteilt ist, ergibt sich sowohl im ''[[Best Case|best]]'' als auch im ''average case'' des Verfahrens eine [[Zeitkomplexität|Laufzeit]] von <math>\mathcal{O} (n)</math>. 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 <math>\mathcal{O} (n\cdot \log n)</math>.

== Literatur ==
* {{Literatur| Autor=Torben Hagerup | Titel=Hybridsort revisited and parallelized | Sammelwerk=Information Processing Letters | Band=32 | Nummer=1 | Seiten=35-39 | Jahr=1989 | DOI=10.1016/0020-0190(89)90066-5 }}
* {{Literatur| Autor=Henk Meijer und Selim G. Akl | Titel=The design and analysis of a new hybrid sorting algorithm | Sammelwerk=Information Processing Letters | Band=10 | Nummer=4,5 | Seiten=213-218 | Jahr=1980 | DOI=10.1016/0020-0190(80)90143-X }}

[[Kategorie:Sortieralgorithmus]]

Hybridsort - Versionsgeschichte

2001:9E8:B326:F000:3943:7460:6659:8E95: /* Komplexität */