Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Stable sorting in Perl

by sweetblood (Parson)
on Aug 27, 2003 at 18:44 UTC ( #287131=perlquestion: print w/ replies, xml ) Need Help??
sweetblood has asked for the wisdom of the Perl Monks concerning the following question:

Is there a way to specify a stable sort? That is a sort where the non-keyed fields remain in natural order after the sort(fifo). I am of course presuming that Perl’s default behavior would be a more efficient unstable sort. If my assumption is incorrect then is there a way to specify an unstable sort to increase sorting performance?

Comment on Stable sorting in Perl
Re: Stable sorting in Perl
by liz (Monsignor) on Aug 27, 2003 at 18:59 UTC
    This might be an answer to your question. From perldoc sort:

    NAME
           sort - perl pragma to control sort() behaviour
    
    SYNOPSIS
               use sort 'stable';          # guarantee stability
               use sort '_quicksort';      # use a quicksort algorithm
               use sort '_mergesort';      # use a mergesort algorithm
               use sort 'defaults';        # revert to default behavior
               no  sort 'stable';          # stability not important
    
               use sort '_qsort';          # alias for quicksort
    
               my $current = sort::current();      # identify prevailing algorithm
    

    Liz

      In case you aren't on the leading edge of Perl versions and don't have sort.pm, you can get a stable sort fairly easily:

      # Replace: my @sorted= sort @list; # with: my @index= sort { $list[$a] cmp $list[$b] || $a <=> $b } 0..$#list; my @sorted= @list[@index]; # or with (to avoid @index remaining in scope): my @sorted= @list[ sort { $list[$a] cmp $list[$b] || $a <=> $b } 0..$#list ];
      For a more complex form of sort:
      # Replace: my @sorted= map { RESTORE($_) } sort { COMPARE($a,$b) } map { XFORM($_) } @list; # with: my @sortOn= map { XFORM($_) } @list; my @index= sort { COMPARE($sortOn[$a],sortOn[$b]) || $a <=> $b } 0..$#sortOn; my @sorted= @list[@index]; # or with (to avoid temporaries remaining in scope): my @sorted= do { my @sortOn= map { XFORM($_) } @list; @list[ sort { COMPARE($sortOn[$a],sortOn[$b]) || $a <=> $b } 0..$#sortOn; ]; };
      Note that this allows us to avoid the RESTORE() step which often means that the XFORM() step becomes much simpler.

      If you are going for speed by avoiding COMPARE() [the advantage of which has been reduced (but not eliminated) for some cases due to new optimizations], then consider:

      # Replace: my @sorted= map { RESTORE($_) } sort map { XFORM($_) } @list; # with:
      my @sorted= @list[ map { unpack "N", substr($_,-4) } sort map { XFORM($list[$_]) . pack "N", $_ } 0..$#list ];
      Which may become my favorite sorting technique because it gives you almost maximum speed while not requiring RESTORE() (which is often the hardest part).

      I like it so much, I've made it an official snippet: fast, flexible, stable sort.

      (updated.)

                      - tye
        This is perfect ... I'm going to pin this to the wall of my cube! ++
        Sorry, maybe I just don't get it, but why is your first example a stable sort?
        my @unsorted = ([1,1], [2,1], [1,2], [2,2], [2,3], [1,3], [2,4], [1,4]); print join( ' ', map { $_->[0].$_->[1] } sort { $a->[0] <=> $b->[0] } @unsorted) . "\n"; my @sortedindices = sort { $unsorted[$a]->[0] <=> $unsorted[$b]->[0] } 0..$#unsorted; print join ( ' ', map { $_->[0].$_->[1] } @unsorted[@sortedindices]); __END__ 11 12 13 14 23 21 24 22 11 12 13 14 23 21 24 22
        Both sorts are not stable.

        daniel.

        update: got it now ;-) replace compare-function by
        $unsorted[$a]->[0] <=> $unsorted[$b]->[0] || $a <=> $b
      I saw a reference to that pragma somewhere on the internet however I don't get that when I do "perldoc -f sort". If I try use sort 'stable'; (et-al) I get: "Can't locate sort.pm ..." etc.
      Do I have to have a seperate sort.pm from cpan? Or (and maybe this is most likely) is this not available in perl v5.6.0?
      But thanks for the reply. ++
        There is a subtle difference between:
        perldoc sort
        
        and
        perldoc -f sort
        
        The former gives you the documentation of the sort pragma, whereas the latter gives you the documentation of the sort function. But indeed, you appear to need at least 5.8.0 for the sort pragma.

        Liz

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://287131]
Approved by VSarkiss
Front-paged by tye
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (12)
As of 2014-08-28 07:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (257 votes), past polls