Re: sort != sort

You can also use bucket sort for this, it can be faster. I.e.

my @sorted; 
push(@{$sorted[_$->{'num'}-1]}, $_) foreach @Objs;
[download]

sorted(x) will then contain items with num=x+1

Comment on Re: sort != sort Download Code

Replies are listed 'Best First'.
Re^2: sort != sort by halfcountplus (Hermit) on Oct 25, 2010 at 19:18 UTC
Wow, I like that -- thanks much! Guaranteed O(n) -- right now, the comparisons are about 120% of n with normative mergesort and 102% of n with quicksort. I can pop those into the new array meaning the memory use will remain flat (rather than temporarily doubling). `my @bucket = (); while($#Notes >= 0) { my $n = shift @Notes; push @{$bucket[$n->{terms}-1]},$n; } #Need 1D array back: while($#bucket >= 0) { my $b = pop @bucket; push @Notes, shift @$b while ($#{$b} >= 0); }` [download] Works perfect.	[reply] [d/l]

Replies are listed 'Best First'.

Re^2: sort != sort
by halfcountplus (Hermit) on Oct 25, 2010 at 19:18 UTC

Guaranteed O(n) -- right now, the comparisons are about 120% of n with normative mergesort and 102% of n with quicksort.
I can pop those into the new array meaning the memory use will remain flat (rather than temporarily doubling).

my @bucket = ();
while($#Notes >= 0) {
    my $n = shift @Notes;
    push @{$bucket[$n->{terms}-1]},$n;
}
#Need 1D array back:
while($#bucket >= 0) {
    my $b = pop @bucket;
    push @Notes, shift @$b while ($#{$b} >= 0);
}
[download]

[reply]
[d/l]