The function q489 computes a single sample quantile using a
fortran implementation of the Floyd and Rivest (1975) algorithm.
In contrast to the more elaborate function kuantile that uses
the Kiweil (2005) implementation it does not attempt to replicate the
nine varieties of quantiles as documented in the base function.
quantile
q489(x, tau = .5)A scalar quantile of the same length as the vector p.
numeric vector
the quantile of intereste.
R.W.Floyd and R.L.Rivest, R implementation: Roger Koenker
This is a direct translation of the Algol 68 implementation of
Floyd and Rivest (1975), implemented in Ratfor. For the median, average
case behavior requires \(1.5 n + O((n log n)^{1/2})\) comparisons.
In preliminary experiments it seems to be somewhat faster in large samples
than the implementation kuantile of Kiwiel (2005). See Knuth (1998)
for further details. No provision is made for non-uniqueness of the quantile.
so, when \(\tau n\) is an integer there may be some discrepancy.
R.W. Floyd and R.L. Rivest: "Algorithm 489: The Algorithm SELECT---for Finding the $i$th Smallest of $n$ Elements", Comm. ACM 18, 3 (1975) 173,
K.C. Kiwiel: On Floyd and Rivest's SELECT Algorithm, Theoretical Computer Sci. 347 (2005) 214-238.
D. Knuth, The Art of Computer Programming, Volume 3, Sorting and Searching, 2nd Ed., (1998), Addison-Wesley.