Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change

Re^2: Numeric sorting WITHOUT <=>

by tobyink (Abbot)
on Oct 10, 2012 at 09:30 UTC ( #998182=note: print w/ replies, xml ) Need Help??

in reply to Re: Numeric sorting WITHOUT <=>
in thread Numeric sorting WITHOUT <=>

And here's a Perl 5.16 implementation of quicksort...

use v5.16; my @sorted = (sub { return @_ unless @_ > 1; my $pivot = splice(@_, int(@_/2), 1); my (@small, @big); push @{ $_ < $pivot ? \@small : \@big }, $_ for @_; return (__SUB__->(@small), $pivot, __SUB__->(@big)) })->(@unsorted);

Can be made a little neater using List::MoreUtils...

use v5.16; use List::MoreUtils 'part'; my @sorted = (sub { return @_ unless @_ > 1; my $pivot = splice(@_, int(@_/2), 1); my ($small, $big) = part { $_ > $pivot } @_; return (__SUB__->(@$small), $pivot, __SUB__->(@$big)) })->(@unsorted);

In older Perls, without __SUB__ you can't recursively call a truly anonymous sub, so you need to have some kind of way of referring to the sub, such as assigning it to a lexical variable...

my @sorted = do { my $SUB; $SUB = sub { return @_ unless @_ > 1; my $pivot = splice(@_, int(@_/2), 1); my (@small, @big); push @{ $_ < $pivot ? \@small : \@big }, $_ for @_; return ($SUB->(@small), $pivot, $SUB->(@big)) }}->(@array);
perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'

Comment on Re^2: Numeric sorting WITHOUT <=>
Select or Download Code
Re^3: Numeric sorting WITHOUT <=>
by ikegami (Pope) on Oct 10, 2012 at 18:25 UTC
    sort uses mergesort by default, not quicksort. That could be a more appropriate choice?

    Your last snippet has a memory leak.

      Mergesort is more complex to implement I think, though not massively so. Perl did once use quicksort, but it was changed in 5.8. The old sorting algorithm can be enabled using:

      use sort '_quicksort';

      Memory leak... indeed. Is it too early to be getting sick of pre-5.16 Perls? In practice you'd probably give the sub a name so this wouldn't be an issue.

      perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'
        Actually, a naïve merge sort is dead simple. Quite possibly the easiest to explain, too.
        sub mergesort { return $_[0] if @_ == 1; my $i = int( @_ / 2 ); my @a = mergesort(@_[0..$i-1]); my @b = mergesort(@_[$i..$#_]); my @sorted; while (@a && @b) { if ($a[0] < $b[0]) { push @sorted, shift(@a); } elsif ($b[0] < $a[0]) { push @sorted, shift(@b); } else { push @sorted, shift(@a), shift(@b); } } return ( @sorted, @a, @b ); }

        lol! I got two 5.8.8 question this week. It'll be a while before it's ok to be sick of 5.14.

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (16)
As of 2014-07-10 19:58 GMT
Find Nodes?
    Voting Booth?

    When choosing user names for websites, I prefer to use:

    Results (215 votes), past polls