Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked

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?

Replies are listed 'Best First'.
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:

           sort - perl pragma to control sort() behaviour
               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


      In case you aren't on the leading edge of Perl versions and don't have, 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.


                      - tye
        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.


        update: got it now ;-) replace compare-function by
        $unsorted[$a]->[0] <=> $unsorted[$b]->[0] || $a <=> $b
        This is perfect ... I'm going to pin this to the wall of my cube! ++
      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 ..." etc.
      Do I have to have a seperate 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
        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.


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://287131]
Approved by VSarkiss
Front-paged by tye
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (6)
As of 2017-06-24 19:51 GMT
Find Nodes?
    Voting Booth?
    How many monitors do you use while coding?

    Results (562 votes). Check out past polls.