UNIVERSITÄTSBIBLIOTHEK

Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning and Its Practical Potential

  • Multiway Quicksort, i.e., partitioning the input in one step around several pivots, has received much attention since Java 7’s runtime library uses a new dual-pivot method that outperforms by far the old Quicksort implementation. The success of dual-pivot Quicksort is most likely due to more efficient usage of the memory hierarchy, which gives reason to believe that further improvements are possible with multiway Quicksort. In this dissertation, I conduct a mathematical average-case analysis of multiway Quicksort including the important optimization to choose pivots from a sample of the input. I propose a parametric template algorithm that covers all practically relevant partitioning methods as special cases, and analyze this method in full generality. This allows me to analytically investigate in depth what effect the parameters of the generic Quicksort have on its performance. To model the memory-hierarchy costs, I also analyze the expected number of scanned elements, a measure for the amount of data transferred from memory that is known to also approximate the number of cache misses very well. The analysis unifies previous analyses of particular Quicksort variants under particular cost measures in one generic framework. A main result is that multiway partitioning can reduce the number of scanned elements significantly, while it does not save many key comparisons; this explains why the earlier studies of multiway Quicksort did not find it promising. A highlight of this dissertation is the extension of the analysis to inputs with equal keys. I give the first analysis of Quicksort with pivot sampling and multiway partitioning on an input model with equal keys.
  • Seit in Version 7 der Java runtime library ein neuer dual-pivot Quicksort zum Einsatz kommt, der deutlich schneller als die vorherige Implementierung arbeitet, hat multiway Quicksort, also das Partitionierung bzgl. mehrerer Pivotelemente zugleich, einige Aufmerksamkeit auf sich gezogen. Der Erfolg von dual-pivot Quicksort ist höchstwahrscheinlich auf eine effizientere Verwendung der Speicherhierarchie zurückzuführen, was Grund zu der Annahme gibt, dass weitere Verbesserungen mit multiway Quicksort möglich sind. In dieser Dissertation wird die mathematische Average-Case-Analyse von multiway Quicksort beschrieben, wobei ausdrücklich die wichtige Optimierung, die Pivotelemente aus einem Sample der Eingabe zu ziehen, das sogenannte pivot sampling, berücksichtigt wird. Dazu wird ein parametrischer Algorithmus vorgestellt und symbolisch in seinen Parametern analysiert, der alle in der Praxis relevanten Partitionierungsmethoden als Spezialfall abdeckt. Das ermöglicht eine detaillierte analytische Untersuchung des Effekts, den die Wahl der verschiedenen Parameter auf die Effizienz des Verfahrens hat. Um Kosten bzgl. der Speicherhierarchie zu modellieren, wird das Kostenmaß “scanned elements” verwendet, dem die mit dem Hauptspeicher ausgetauschte Datenmenge zugrunde liegt, und das bekanntermaßen die Anzahl an cache misses gut approximiert. Die Analyse in dieser Arbeit vereinheitlicht frühere Untersuchungen konkreter Partitionierungsmethoden bzgl. bestimmter Kostenmaße unter dem Dach einer vereinheitlichten Theorie. Ein Ergebnis dieser Arbeit ist, dass multiway Quicksort deutliche Vorteile bzgl. des Kostenmaßes scanned elements bringen kann, während die Anzahl Schlüsselvergleiche nicht wesentlich verbessert wird. Das ist eine mögliche Erklärung, warum multiway Quicksort nicht schon in der Vergangenheit als vielversprechende Variante angesehen wurde. Darüber hinaus gelang in dieser Dissertation erstmals die Verallgemeinerung der Analyse von Quicksort mit multiway partitioning und pivot sampling auf Eingaben mit gleichen Schlüsseln.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Sebastian Wild
URN (Permalink):urn:nbn:de:hbz:386-kluedo-44682
Betreuer:Markus Nebel
Dokumentart:Dissertation
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):10.10.2016
Jahr der Veröffentlichung:2016
Veröffentlichende Institution:Technische Universität Kaiserslautern
Titel verleihende Institution:Technische Universität Kaiserslautern
Datum der Annahme der Abschlussarbeit:07.08.2016
Datum der Publikation (Server):12.10.2016
Freies Schlagwort / Tag:Quicksort; Yaroslavskiy-Bentley-Bloch Quicksort; analysis of algorithms; average-case analysis; continuous master theorem; multiway partitioning; pivot sampling
Seitenzahl:XVI, 357
Fachbereiche / Organisatorische Einheiten:Fachbereich Informatik
CCS-Klassifikation (Informatik):F. Theory of Computation / F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY (B.6-7, F.1.3) / F.2.2 Nonnumerical Algorithms and Problems (E.2-5, G.2, H.2-3) / Sorting and searching
DDC-Sachgruppen:0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik
5 Naturwissenschaften und Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vom 30.07.2015