Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"

Re^2: Stable sorting in Perl (old)

by tye (Sage)
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, 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

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


    update: got it now ;-) replace compare-function by
    $unsorted[$a]->[0] <=> $unsorted[$b]->[0] || $a <=> $b
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? :-)


      <Elian> And I do take a kind of perverse pleasure in having an OO assembly language...

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://287141]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (4)
As of 2017-06-24 18:08 GMT
Find Nodes?
    Voting Booth?
    How many monitors do you use while coding?

    Results (562 votes). Check out past polls.