Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Re: crop-sort: Maintaining a Top-10 Array

by wog (Curate)
on Nov 10, 2001 at 21:11 UTC ( #124567=note: print w/replies, xml ) Need Help??


in reply to crop-sort: Maintaining a Top-10 Array

Alternately, one could use a binary search to find where to insert and then insert. The binary search has O(log N) time.

sub crop_binary_insert { my ($a, $x) = @_; my ($min, $max) = (0, $#{$a}); return if ($a->[-1] >= $x); # don't bother to insert if we don't hav +e to while ($min != $max) { my $mid = int( ($min + $max)/2 ); if ($a->[$mid] > $x) { $min = $mid+1; } else { $max = $mid; } } pop @$a; splice @$a, $min, 0, $x; }

update: fixed up indention slightly.

update 2: s/\$i/\$mid/ (Oops! Thanks to petral.)

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://124567]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (9)
As of 2022-11-29 22:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?