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.
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;
}
In practice it's pretty inefficient, and even proving that it runs in linear time is not entirely trivial!
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|