Re^2: Stable sorting in Perl (old)

[tye]

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

[sweetblood]

This is perfect ... I'm going to pin this to the wall of my cube! ++

[demerphq]

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

[wirrwarr]

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