crop-sort: Maintaining a Top-10 Array

Assuming you have a sorted array of scores (it doesn't have to be 10 of them) with the highest first and the lowest last, you probably want to update the list in regards to a new score. Here's an efficient way to do it that doesn't use Perl's builtin sort(), and works in O(N) time.

sub crop_sort {
  my ($a, $x) = @_;

  if ($a->[-1] < $x) { $a->[-1] = $x }
  else { return }

  for (my $i = @$a - 2; $i >= 0; $i--) {
    if ($a->[$i] < $a->[$i+1]) {
      @$a[$i,$i+1] = @$a[$i+1,$i];
    }
    else { last }
  }
}
[download]

I called it crop-sort even though it's just a one-pass bubble-sort because of its behavior. It effectively adds an element to the array and bubbles its way to the proper location, and then removes the least element. Except it does it a little smarter than that -- if the new element is smaller than any other, the function returns immediately. Otherwise, the l(e)ast element is replaced by the new element, and the bubbling occurs. This is at most O(N) time if the new element happens to be larger than all the others.

Comment on crop-sort: Maintaining a Top-10 Array Download Code

Replies are listed 'Best First'.
Re: crop-sort: Maintaining a Top-10 Array by wog (Curate) on Nov 10, 2001 at 21:11 UTC
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; }` [download] update: fixed up indention slightly. update 2: `s/\$i/\$mid/` (Oops! Thanks to petral.)	[reply] [d/l] [select]
Re: crop-sort: Maintaining a Top-10 Array by merlyn (Sage) on Nov 11, 2001 at 17:37 UTC
I think you're swapping unnecessarily. Consider this algorithm: start with item n where n = 10. if my insert item is less than that, exit if my insert item is bigger than item n, then set item n to my insert item, and quit reduce n by 1, copy item n to item n+1 and repeat from the previous step See.. I don't see any swaps needed. Just a push-down. Of course, if you find the location using a binary search, it might be faster, and then use a splice to insert it, and you're now at the other algorithm. {grin} -- Randal L. Schwartz, Perl hacker	[reply]
(tye)Re: crop-sort: Maintaining a Top-10 Array by tye (Sage) on Nov 12, 2001 at 23:06 UTC
This task is a perfect match for a heap sort. See Heap for a module that implements a huge variety of heaps. - tye (but my friends call me "Tye")	[reply]