medianOfMedians

[Andrei Alexandrescu via Digitalmars-d]

On 01/19/2016 09:26 PM, Timon Gehr wrote:
> On 01/20/2016 02:20 AM, Andrei Alexandrescu wrote:
>> I've seldom have code write itself so beautifully. Which, of course,
>> means it needs to be destroyed.
>> https://github.com/D-Programming-Language/phobos/pull/3938 -- Andrei
>
> This is not an implementation of the median of medians algorithm.
>
> int[] bad(int n){
>      if(n<=5){ return iota(n).array; }
>      auto next=bad(n/5);
>      return next.map!(a=>[a-2,a-1,a,a+n,a+n+1]).join;
> }
>
> void main(){
>      import std.stdio;
>      auto a=bad(5^^10);
>      auto idx=medianOfMedians(a);
>      double notLarger=a.count!(x=>x<=a[idx])/(1.0*a.length);
>      writeln(notLarger); // 0.0100766
>      assert(notLarger>=0.3); // fail
> }
>
> The real algorithm works by computing an /exact/ median of the medians
> and uses it as the pivot value for quickselect in order to compute the
> precise median of the full array. In the given implementation, the
> approximations accumulate with each recursive invocation and no constant
> guarantees can be given on the percentile of the result.

Thanks. Urgh. So the approximate median part cannot be separated from 
partitioning. It was suspiciously cute :o). Back to the drawing board. 
-- Andrei