We present an efficient algorithm for the approximate median selection problem. The algorithm works
in-place; it is fast and easy to implement. For a large array it returns, with high probability, a very close estimate of the true
median. The running time is linear in the length
n of the input. The algorithm performs fewer than
$
\frac{4}
{3}n
$
\frac{4}
{3}n
comparisons and
$
\frac{1}
{3}n
$
\frac{1}
{3}n
exchanges on the average. We present analytical results of the performance of the algorithm, as well as experimental illustrations
of its precision.
keywords Approximation algorithms - in-place algorithms - median selection - analysis of algorithms