Bibliography | Heidenwag, Jarkko: Durchschnittsanalyse für Quicksort mit Links-Rechts-Partitionierung im Fall vieler Duplikate. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 73 (2018). 23 pages, german.
|
Abstract | Das Ziel dieser Arbeit besteht darin, die relativ neue und dementsprechend unerforschte Idee der Links-Rechts-Partitionierung genauer zu untersuchen. Schon bei oberflächlicher Betrachtung des Algorithmus fällt auf, dass sich diese Partitionierungsstrategie für Quicksort besonders gut für Datensätze, wie sie in realen Systemen verarbeitet werden, eignen sollte und Benchmarks bestätigen diese Annahme. Um die Effizienz des Sortierverfahrens auch theoretisch besser begründen zu können, wird, nachdem der Algorithmus beschrieben und in Pseudocode verfasst wurde, eine mit seiner Rekursion vergleichbare Struktur in Binärbäumen gesucht. Hierdurch wird erkenntlich, dass seine Vergleichskosten zum Sortieren einer Eingabe der Länge N, mit u N paarweise verschiedenen Elementen, wie intuitiv vermutet, O¹N log¹uºº betragen. Auch die linearen Kosten des Best Case und der Worst Case von O¹N uº werden durch diese Äquivalenz bestätigt, wodurch also in beiden Fällen weniger Vergleiche benötigt werden, als bei einer Sortierung mit klassischem Quicksort. Um die zu erwartenden Vergleiche einer Sortierung genauer zu bestimmen, wird eine Rekursionsgleichung für eine obere Schranke dieser Anzahl berechnet, wobei das Ergebnis in Abhängigkeit der Entropie der Eingabe angegeben wird.
|
Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
|
Superviser(s) | Diekert, Prof. Volker; Weiß, Dr. Armin |
Entry date | May 16, 2019 |
---|