q489 {quantreg}

Even Quicker Sample Quantiles

Description

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

Usage

q489(x, tau = .5) 

Arguments

x

numeric vector

tau

the quantile of intereste.

Details

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.

Value

A scalar quantile of the same length as the vector p.

Author(s)

R.W.Floyd and R.L.Rivest, R implementation: Roger Koenker

References

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.

See Also

quantile

Examples

     medx <- q489(rnorm(1001))