ALCOMFT-TR-03-2

Conrado Mart\'\inez, Daniel Panario and Alfredo Viola
Adaptive Sampling for Quickselect
Barcelona. Work packages 1 and 4. April 2003.

Abstract: There are several detailed analysis for the median-of-(2t+1) variant of quickselect, and in particular for median-of-3, but no previous results were known for the following natural variant: ``we choose the smallest of the sample if the rank of the sought element is small, the largest of the sample if the sought rank is large, and the median if the rank is medium.'' We tackle here this question and provide a precise answer about the asymptotic average cost for the cases where samples of 2 and 3 elements are used. We also consider the more general case of samples with s > 3 elements and study some of the interesting features of this natural sampling strategy using numerical approximations.

Postscript file: ALCOMFT-TR-03-2.ps.gz (109 kb).