UNIVERSITÄTSBIBLIOTHEK

Java 7's Dual Pivot Quicksort

  • Recently, a new Quicksort variant due to Yaroslavskiy was chosen as standard sorting method for Oracle's Java 7 runtime library. The decision for the change was based on empirical studies showing that on average, the new algorithm is faster than the formerly used classic Quicksort. Surprisingly, the improvement was achieved by using a dual pivot approach — an idea that was considered not promising by several theoretical studies in the past. In this thesis, I try to find the reason for this unexpected success. My focus is on the precise and detailed average case analysis, aiming at the flavor of Knuth's series “The Art of Computer Programming”. In particular, I go beyond abstract measures like counting key comparisons, and try to understand the efficiency of the algorithms at different levels of abstraction. Whenever possible, precise expected values are preferred to asymptotic approximations. This rigor ensures that (a) the sorting methods discussed here are actually usable in practice and (b) that the analysis results contribute to a sound comparison of the Quicksort variants.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Sebastian Wild
URN (Permalink):urn:nbn:de:hbz:386-kluedo-34638
Betreuer:Markus Nebel
Dokumentart:Masterarbeit
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):04.03.2013
Jahr der Veröffentlichung:2012
Veröffentlichende Institution:Technische Universität Kaiserslautern
Titel verleihende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):18.04.2013
Freies Schlagwort / Tag:analysis of algorithms
Seitenzahl:171
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)
G. Mathematics of Computing / G.2 DISCRETE MATHEMATICS
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)
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
G. Mathematics of Computing / G.2 DISCRETE MATHEMATICS / G.2.1 Combinatorics (F.2.2)
G. Mathematics of Computing / G.2 DISCRETE MATHEMATICS / G.2.1 Combinatorics (F.2.2) / Recurrences and difference equations
DDC-Sachgruppen:0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vom 10.09.2012