note
robin
As [ambrus] said, even the warm-up problem is pretty damned hard. I too cheated by looking in Cormen, Leiserson and Rivest. Here is a Perl implementation of the linear-time algorithm they give.
<code>
sub naive_median {
(sort {$a <=> $b} @_)[@_/2];
}
sub nth_largest {
my ($n, @a) = @_;
die "You can't find the ${n}th-largest element of an ".@a."-element array!"
if $n > $#a || $n < 0;
#warn "Looking for ${n}th element of (@a)\n";
return $a[0] if $n == 0;
my @medians;
for(my $i=0; $i < @a; $i += 5) {
push @medians, naive_median(@a[$i..($i+4 > $#a ? $#a : $i+4)]);
}
my $median = median(@medians);
my @smaller = grep {$_ < $median} @a;
return nth_largest($n, @smaller) if $n < @smaller;
my @larger = grep {$_ >= $median} @a;
return nth_largest($n - @smaller, @larger);
}
sub median {
unshift @_, int(@_/2);
goto &nth_largest;
}
</code>
In practice it's pretty inefficient, and even proving that it runs in linear time is not entirely trivial!
509409
509409