Wild, Sebastian ORCID: 0000-0002-6061-9177, Nebel, Markus E and Mahmoud, Hosam
(2016)
Analysis of Quickselect Under Yaroslavskiy’s Dual-Pivoting Algorithm.
Algorithmica: an international journal in computer science, 74 (1).
pp. 485-506.
This is the latest version of this item.
Text
quickselect-paper.pdf - Author Accepted Manuscript Download (229kB) | Preview |
Abstract
There is excitement within the algorithms community about a new partitioning method introduced by Yaroslavskiy. This algorithm renders Quicksort slightly faster than the case when it runs under classic partitioning methods. We show that this improved performance in Quicksort is not sustained in Quickselect; a variant of Quicksort for finding order statistics. We investigate the number of comparisons made by Quickselect to find a key with a randomly selected rank under Yaroslavskiy’s algorithm. This grand averaging is a smoothing operator over all individual distributions for specific fixed order statistics. We give the exact grand average. The grand distribution of the number of comparison (when suitably scaled) is given as the fixed-point solution of a distributional equation of a contraction in the Zolotarev metric space. Our investigation shows that Quickselect under older partitioning methods slightly outperforms Quickselect under Yaroslavskiy’s algorithm, for an order statistic of a random rank. Similar results are obtained for extremal order statistics, where again we find the exact average, and the distribution for the number of comparisons (when suitably scaled). Both limiting distributions are of perpetuities (a sum of products of independent mixed continuous random variables).
Item Type: | Article |
---|---|
Additional Information: | full version with appendices; otherwise identical to Algorithmica version |
Uncontrolled Keywords: | Quicksort, Quickselect, Average-case analysis, Grand average, Contraction |
Depositing User: | Symplectic Admin |
Date Deposited: | 22 Oct 2019 14:27 |
Last Modified: | 19 Jan 2023 00:21 |
DOI: | 10.1007/s00453-014-9953-x |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3059080 |
Available Versions of this Item
-
Analysis of Quickselect Under Yaroslavskiy's Dual-Pivoting Algorithm. (deposited 21 Oct 2019 14:06)
- Analysis of Quickselect Under Yaroslavskiy’s Dual-Pivoting Algorithm. (deposited 22 Oct 2019 14:27) [Currently Displayed]