Le 18/09/2010 20:43, Dimitri Pourbaix a écrit :
> Luc,
>
>>> On the other hand, the speedup 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 worstcase
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 commonsmath. An average linear
behavior and worstcase 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 : +322650.35.71
> B1050 Bruxelles * Fax : +322650.42.26
> http://sb9.astro.ulb.ac.be/~pourbaix * mailto:pourbaix@astro.ulb.ac.be
>
> 
> To unsubscribe, email: devunsubscribe@commons.apache.org
> For additional commands, email: devhelp@commons.apache.org
>

To unsubscribe, email: devunsubscribe@commons.apache.org
For additional commands, email: devhelp@commons.apache.org
