Le 18/09/2010 20:43, Dimitri Pourbaix a écrit : > Luc, > >>> On the other hand, the speed-up version would no longer >>> be mathematically correct, as a rough approximate of the pivot would be >>> adopted. >> >> No, the exact pivot is used. Its evaluation is only delayed. It would be >> correct. > > Given a **general** array, I do not think one can identify the median in > just n iterations (i.e. reading the array only once).
It is possible using Blum, Floyd, Pratt, Rivest and Tarjan, or David R. Musser introselect algorithm (which uses BFPRT under the hood). See <http://www.cs.rpi.edu/~musser/gp/introsort.ps> for the original paper Unfortunately, despite the paper says another paper will be devoted to introselect I did not find it and suspect it was never published. The Blum, Floyd, Pratt, Rivest and Tarjan algorithm ensure linear worst-case behaviour is depicted here: <http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm>. I'm not sure it is *really* needed to go to these lengths and have a guaranteed linear worst case behavior in commons-math. An average linear behavior and worst-case O(n^2) may be sufficient in many cases. Also starting with Hoare selction algorithm and adding BFPRT in a later version is always possible as Musser's algorithm simply switch from Hoare to BFPRT when it detects arrays splitting are not sufficiently efficients. Luc > > Dim. > ---------------------------------------------------------------------------- > > Dimitri Pourbaix * > Institut d'Astronomie et d'Astrophysique * Don't worry, be happy > CP 226, office 2.N4.211, building NO * and CARPE DIEM. > Universite Libre de Bruxelles * > Boulevard du Triomphe * Tel : +32-2-650.35.71 > B-1050 Bruxelles * Fax : +32-2-650.42.26 > http://sb9.astro.ulb.ac.be/~pourbaix * mailto:pourb...@astro.ulb.ac.be > > --------------------------------------------------------------------- > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
