Analysis of Quickselect under Yaroslavskiy’s Dual-Pivoting Algorithm

In this paper, we analyze the number of comparisons used by Quickselect to find a randomly chosen order statistic when we use YBB partitioning instead of the ordinary binary partitioning. We compute exact averages and limit distributions for that.

All results are without pivot sampling, but the asymptotic results can easily be generalized to pivot sampling; see the slides.

Unlike for Quicksort, dual-pivoting does not save comparisons in Quickselect. Intuitively, this is because whenever we continue recursively in the left- or rightmost segment, the subdivision of the discarded part was in vain.

Cache Misses in Quickselect

Unfortunately, we finished this article before Kushagra et al. published their results on multi-pivot Quicksort and cache misses. In terms of scanned elements, our machine-independent model of cache behavior (see our paper for details), Quickselect in fact slightly improves using YBB partitioning: asymptotically $2.\overline6 n$ vs. $3 n$ in the grand average, a reduction of 12.5%.

According to quick running time tests, classic and YBB Quickselect do not differ measurably in average running time, though.

Relation to Other Papers

The analysis reuses results on the partitioning method derived about Quicksort in our TALG paper.

Intended Audience

algorithms experts, mathematically inclined computer scientists.