Alfredo Viola (Université de Montevideo, Uruguay)

The median-of-3 variant of quickselect has been largely studied. However, the following natural adaptive variant had not been analyzed: choose as pivot the smallest of the sample if the rank of the sought element is small, the largest if the rank is large, and the median if the rank is medium.

We first analyze proportional-of-2 and proportional-of-3 in which we use equal-size intervals. We propose $\nu$-find, a generalization of median-of-3 and proportional-of-3 with interval breakpoints $\nu$ and $1-\nu$.

We give the optimal $\nu$ and values for which $\nu$-find outperforms median- of-3.

The talk will be concentrated in the algorithmic aspects of the problem, as well as how its analysis contributes to the understanding of the most delicate parts of them.

This is a joint work with Conrado Martinez and Daniel Panario.