Katharina Klost:

Details on the Integer Sorting Algorithm by Han and Thorup Using O(n sqrt(loglog n)) Time and Linear Space

Kurzbeschreibung

Sortieren ist eines der grundlegenden Probleme in der Informatik. Die Zeitkomplexität für vergleichsbasiertes Sortieren ist bekanntermaßen Theta(n log n). Wenn nun die Eingaben auf Integer beschränkt werden und eine RAM mit einer beschränkten und von der Eingabegröße abhängigen Wortlänge als Modell für die Komplexitätsanalyse gewählt wird, kann diese Schranke unterschritten werden. Die Beschränkung der Wortlänge ist notwendig um reale Einschränkungen abbilden zu können. Die Frage ob mit diesen Vorraussetzungen in linearer Zeit sortiert werden kann ist noch offen.
Der in der Arbeit vorgestellte Algorithmus von Han und Thorup kombiniert bekannte Algorithmen für die Sortierung von Integern mit einem neuen Algorithmus der eine Eingabemenge in kleinere Mengen auf denen eine gewisse Ordnung definiert ist aufteilt. Somit wird eine Komplexität von O(n sqrt(log log n)) für das randomisierte Sortieren beliebig langer Integer erreicht. 

Abschluss
Bachelor of Science (B.Sc.)
Abgabedatum
15.01.2015
Homepage des Autors