Nebel, Markus E and Wild, Sebastian 
ORCID: 0000-0002-6061-9177
(2014)
Pivot Sampling in Dual-Pivot Quicksort.
.
|
Text
nebel-wild-2014.pdf - Author Accepted Manuscript Download (894kB) | Preview |
Abstract
The new dual-pivot Quicksort by Vladimir Yaroslavskiy - used in Oracle's Java runtime library since version 7 - features intriguing asymmetries in its behavior. They were shown to cause a basic variant of this algorithm to use less comparisons than classic single-pivot Quicksort implementations. In this paper, we extend the analysis to the case where the two pivots are chosen as fixed order statistics of a random sample and give the precise leading term of the average number of comparisons, swaps and executed Java Bytecode instructions. It turns out that - unlike for classic Quicksort, where it is optimal to choose the pivot as median of the sample - the asymmetries in Yaroslavskiy's algorithm render pivots with a systematic skew more efficient than the symmetric choice. Moreover, the optimal skew heavily depends on the employed cost measure; most strikingly, abstract costs like the number of swaps and comparisons yield a very different result than counting Java Bytecode instructions, which can be assumed most closely related to actual running time.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Additional Information: | presented at AofA 2014 (http://www.aofa14.upmc.fr/) |
| Uncontrolled Keywords: | cs.DS, cs.DS, math.PR |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 21 Oct 2019 14:07 |
| Last Modified: | 19 Jan 2023 00:21 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3058960 |
Share
Share
