Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re^2: Stable sorting in Perl (old)

by tye (Cardinal)
on Aug 27, 2003 at 19:24 UTC ( #287141=note: print w/ replies, xml ) Need Help??


in reply to Re: Stable sorting in Perl
in thread Stable sorting in Perl

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


Comment on Re^2: Stable sorting in Perl (old)
Select or Download Code
Re: Re^2: Stable sorting in Perl (old)
by sweetblood (Parson) on Aug 27, 2003 at 19:43 UTC
    This is perfect ... I'm going to pin this to the wall of my cube! ++

      tyes node is one of the better collections of the various advanced sorting techniques that I've seen. However you may want to have also have a look at one of PM's earliest nodes, and the canonical Schwartzian Transform (ST), which is the term generally given to most of these techniques in books. There is also the Guttman Rosler Transform (GRT) which is IMO a specialisation of the ST, and of which class I would say that tyes variant belongs to, although I suspect that perhaps it deserves its own name, possibly the Tye Transform? :-)


      ---
      demerphq

      <Elian> And I do take a kind of perverse pleasure in having an OO assembly language...
Re: Re: Stable sorting in Perl (old)
by wirrwarr (Monk) on Aug 28, 2003 at 07:13 UTC
    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

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (5)
As of 2014-07-29 03:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (211 votes), past polls