• search hit 1 of 0
Back to Result List

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.

Download full text files

Export metadata

Metadaten
Author:Sebastian Wild
URN:urn:nbn:de:hbz:386-kluedo-34638
Advisor:Markus Nebel
Document Type:Master's Thesis
Language of publication:English
Date of Publication (online):2013/03/04
Year of first Publication:2012
Publishing Institution:Technische Universität Kaiserslautern
Granting Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2013/04/18
Tag:analysis of algorithms
Page Number:171
Faculties / Organisational entities:Kaiserslautern - Fachbereich Informatik
CCS-Classification (computer science):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-Cassification:0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 10.09.2012