Abstract - hofri (original) (raw)
S�minaire du 3 octobre 05, Micha Hofri, Projet Algo et WPI Computer Science Department, USA.
Analysis of an Algorithm for Approximate Median Selection
We present as simple and efficient algorithm for the approximate median selection problem. The algorithm works in-situ; it is fast and easy to implement. It is also possible to use it "on line," for a stream of data. For a large array it returns, with high probability, a very good estimate of the true median. The running time is linear in the length n of the input: The algorithm performs fewer than frac43n\frac{4}{3}nfrac43n comparisons, and frac13n\frac{1}{3}nfrac13n exchanges on the average.
We show some experimental illustrations of its operation, but most of the talk is about analysis of the quality of the algorithm.
Last modified: Mon May 23 18:32:54 CEST 2005