O(n), not n Expected case is n + n/2 + n/4 ... < 2n
On Sat, Sep 18, 2010 at 12:05 PM, Luc Maisonobe <luc.maison...@free.fr>wrote: > 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 > >
