Analysis of pivot sampling in dual-pivot Quicksort: a holistic analysis of Yaroslavskiy's partitioning scheme
From MaRDI portal
(Redirected from Publication:308946)
Abstract: The new dual-pivot Quicksort by Vladimir Yaroslavskiy - used in Oracle's Java runtime library since version 7 - features intriguing asymmetries. They make a basic variant of this algorithm use less comparisons than classic single-pivot Quicksort. In this paper, we extend the analysis to the case where the two pivots are chosen as fixed order statistics of a random sample. Surprisingly, dual-pivot Quicksort then needs more comparisons than a corresponding version of classic Quicksort, so it is clear that counting comparisons is not sufficient to explain the running time advantages observed for Yaroslavskiy's algorithm in practice. Consequently, we take a more holistic approach and give also the precise leading term of the average number of swaps, the number of executed Java Bytecode instructions and the number of scanned elements, a new simple cost measure that approximates I/O costs in the memory hierarchy. We determine optimal order statistics for each of the cost measures. It turns out that the asymmetries in Yaroslavskiy's algorithm render pivots with a systematic skew more efficient than the symmetric choice. Moreover, we finally have a convincing explanation for the success of Yaroslavskiy's algorithm in practice: Compared with corresponding versions of classic single-pivot Quicksort, dual-pivot Quicksort needs significantly less I/Os, both with and without pivot sampling.
Recommendations
- Pivot sampling in dual-pivot quicksort: exploiting asymmetries in Yaroslavskiy's partitioning scheme
- Optimal partitioning for dual-pivot quicksort
- Average case and distributional analysis of dual-pivot quicksort
- Optimal Partitioning for Dual Pivot Quicksort
- Average case analysis of Java 7's dual pivot quicksort
Cites work
- scientific article; zbMATH DE number 53772 (Why is no real title available?)
- scientific article; zbMATH DE number 718142 (Why is no real title available?)
- scientific article; zbMATH DE number 1540682 (Why is no real title available?)
- An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms
- Analysis of Branch Misses in Quicksort
- Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm
- Asymptotic analysis of an optimized quicksort algorithm.
- Average case analysis of Java 7's dual pivot quicksort
- Average case and distributional analysis of dual-pivot quicksort
- How Branch Mispredictions Affect Quicksort
- Implementing Quicksort programs
- Improved master theorems for divide-and-conquer recurrences
- Increasing the efficiency of quicksort
- Introduction to algorithms.
- Multi-pivot quicksort: theory and experiments
- On a multivariate contraction method for random recursive structures with applications to quicksort
- Optimal Partitioning for Dual Pivot Quicksort
- Optimal sampling strategies in Quicksort and Quickselect
- Order Statistics
- Pivot sampling in dual-pivot quicksort: exploiting asymmetries in Yaroslavskiy's partitioning scheme
- The Influence of Caches on the Performance of Sorting
- The Number of Symbol Comparisons in QuickSort and QuickSelect
- The analysis of Quicksort programs
- The number of bit comparisons used by quicksort: an average-case analysis
Cited in
(9)- Pivot sampling in dual-pivot quicksort: exploiting asymmetries in Yaroslavskiy's partitioning scheme
- Average case analysis of Java 7's dual pivot quicksort
- How good is multi-pivot quicksort?
- Multi-pivot quicksort: theory and experiments
- Dual-pivot quicksort: optimality, analysis and zeros of associated lattice paths
- Optimal Partitioning for Dual Pivot Quicksort
- Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm
- Optimal partitioning for dual-pivot quicksort
- Average case and distributional analysis of dual-pivot quicksort
This page was built for publication: Analysis of pivot sampling in dual-pivot Quicksort: a holistic analysis of Yaroslavskiy's partitioning scheme
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q308946)
