Diploma Thesis DIP-1552

BibliographyLange, Sven: In-Situ-Sortierverfahren.
University of Stuttgart, Faculty of Computer Science, Diploma Thesis No. 1552 (1997).
191 pages, german.
CR-SchemaF.2.2 (Nonnumerical Algorithms and Problems)
KeywordsUltimate Heapsort; Auswahl; Median
Abstract

Jyrki Katajainen stellte 1996 das neue Sortierverfahren Ultimate Heapsort vor, das im worst case $n\log_{2}n + O(n)$ Vergleiche für das Sortieren von $n$ Schlüsseln benötigt. Damit ist die Lücke zwischen unterer Schranke von $\log_{2}(n!)$ Vergleichen und worst case zumindest theoretisch geschlossen. Volker Diekert verbessert Katajainens Ansatz und kann den viel zu hohen positiven Faktor des linearen Terms auf $18$ senken, was im Vergleich zu Bottom--Up--Heapsort für die Praxis immer noch uninteressant ist.

Es zeigt sich, daß eine große Anzahl von Vergleichen für die Lösung des Auswahlproblems verantwortlich für die Höhe des Faktors verantwortlich ist. Daher beschäftigt sich ein Abschnitt dieser Arbeit eingehend mit dem Auswahlproblem und stellt unter anderem ein Verfahren vor, welches das Auswahlproblem im \textit{average case} mit $3/2 \cdot n + o(n)$ Vergleichen lösen kann.

Beide Varianten von Ultimate Heapsort werden mit unterschiedlichen Auswahlverfahren zusammen getestet und empirische Ergebnisse ermittelt. Dabei stellt sich heraus, daß der Faktor im Durchschnitt nicht geringer als $7$ wird. Verglichen mit dem average case des Bottom--Up--Heapsort ist dieser Wert so hoch, daß Ultimate Heapsort für die Praxis uninteressant ist.

Dennoch besteht weiterhin ein theoretisches Interesse an Ultimate Heapsort: Das belegen die Untersuchungen von Laurent Rosaz, der nach eigenen Angaben den linearen Faktor im worst case auf $8$ senken konnte.

Full text and
other links
PostScript (2382752 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
Department(s)University of Stuttgart, Institute of Computer Science, Theoretical Computer Science
Entry dateNovember 20, 1997
   Publ. Computer Science