Making the sort stable in Perl

Question

I have an array of refs with me . Something like

$a[0] = [qw( 1 2 3 4 )];
$a[1] = [qw( a b c d )];

The 1,2,3,4 are actually website breadcrumbs which are used for navigation (Home, Profile, Contact-us, Contact-me-specifically).

Now, I have to sort this ladder (And using stable sort in perl 5.8 is not an option sadly)

The sorting criteria is

1. The depth of the ladder
2. If two ladders have same depth, then sort them depending on their index.

For example, if the array originally contains

$a[0] = [qw( 1 2 3 4 )];
$a[1] = [qw( 1 2 3 )];

Then after the sort, the array should contain

$a[0] = [qw( 1 2 3 )];
$a[1] = [qw( 1 2 3 4 )];

But if the arrays are something like :-

$a[0] = [qw( 1 2 3 )];
$a[1] = [qw( a b c )];

Then after the sort,

$a[0] = [qw( 1 2 3 )];
$a[1] = [qw( a b c )];

I can't get it to work this way that I tried .

my @sorted_array = sort { @$b <=> @$a || $a <=> $b } @a;

Can someone help me in this?

Answer 1

I think we need to clear up your sorting algorithm. You said:

1. The depth of the ladder
2. Sort them depending on their index.

Here's an example:

$array[0] = [ qw(1 a b c d e) ];
$array[2] = [ qw(1 2 b c d e) ];
$array[3] = [ qw(a b c) ];
$array[4] = [ qw(a b c d e) ];

You want them sorted this way:

$array[3] = [ qw(a b c) ];
$array[2] = [ qw(1 2 b c d e) ];
$array[0] = [ qw(1 a b c d e) ];
$array[4] = [ qw(a b c d e) ];

Is that correct?

What about this?

$array[0] = [ qw(100, 21, 15, 32) ];
$array[1] = [ qw(32,  14, 32, 20) ];

Sorting by numeric, $array[1] should be before $array[0], but sorting by string, $array[0] is before $array[1].

Also, you notice that I cannot tell whether $array[0] should be before or after $array[1] until I look at the second element of the array.

This makes sorting very difficult to do on a single line function. Even if you can somehow reduce it, It'll make it very difficult for someone to analyze what you are doing, or for you to debug the statement.

Fortunately, you can use an entire subroutine as a sort routine:

use warnings;
use strict;
use autodie;
use feature qw(say);
use Data::Dumper;

my @array;
$array[0] = [ qw(1 2 3 4 5 6) ];
$array[1] = [ qw(1 2 3) ];
$array[2] = [ qw(a b c d e f) ];
$array[3] = [ qw(0 1 2) ];

my @sorted_array = sort sort_array @array;
say Dumper \@sorted_array;

sub sort_array {
    #my $a = shift;   #Array reference to an element in @array
    #my $b = shift;   $Array reference to an element in @array

    my @a_array = @{ $a };
    my @b_array = @{ $b };

    #
    #First sort on length of arrays
    #
    if ( scalar  @a_array ne scalar  @b_array ) {
        return scalar @a_array <=> scalar @b_array;
    }

    #
    # Arrays are the same length. Sort on first element in array that differs
    #
    for my $index (0..$#a_array ) {
        if ( $a_array[$index] ne $b_array[$index] ) {
            return $a_array[$index] cmp $b_array[$index];
        }
    }
    #
    # Both arrays are equal in size and content
    #
    return 0;
}

This returns:

$VAR1 = [
          [
            '0',
            '1',
            '2'
          ],
          [
            '1',
            '2',
            '3'
          ],
          [
            '1',
            '2',
            '3',
            '4',
            '5',
            '6'
          ],
          [
            'a',
            'b',
            'c',
            'd',
            'e',
            'f'
          ]
        ];

Answer 2

Your code doesn't work because you expect $a and $b to contain the element's value in one place (@$b <=> @$a) and the element's index in another ($a <=> $b).

---

You need the indexes in your comparison, so your comparison function is going to need the indexes.

By passing the indexes of the array to sort, you have access to both the indexes and the values at those indexes, so your code is going to include

sort { ... } 0..$#array;

---

After we're finished sorting, we want to retrieve the elements for those indexes. For that, we can use

my @sorted = map $array[$_], @sorted_indexes;

or

my @sorted = @array[ @sorted_indexes ];

---

All together, we get:

my @sorted =
   map $array[$_],
    sort { @{ $array[$a] } <=> @{ $array[$b] } || $a <=> $b }
      0..$#array;

or

my @sorted = @array[
   sort { @{ $array[$a] } <=> @{ $array[$b] } || $a <=> $b }
     0..$#array
];

Answer 3

The description of your data structure (linked list), and the implementation in your sort routine (arrayrefs) do not quite fit together; I will assume the latter.

A non-stable sort can be made stable by sorting by the position as a secondary criterion:

sort { normally or by_index } @stuff

Normally, you seem to want to compare the array length. To be able to test for the index, you have to somehow make the index of the current element available. You can do so by two means:

1. Do the Schwartzian Transform, and annotate each element with its index. This is silly.
2. Sort the indices, not the elements.

This would look like:

my @sorted_indices =
  sort { @{ $array[$b] } <=> @{ $array[$a] } or $a <=> $b } 0 .. $#array;
my @sorted = @array[@sorted_indices]; # do a slice

What you were previously doing with $a <=> $b was comparing refernces. This is not guaranteed to do anything meaningful.

Test of that sort:

use Test::More;
my @array = (
  [qw/1 2 3/],
  [qw/a b c/],
  [qw/foo bar baz qux/],
);
my @expected = (
  [qw/foo bar baz qux/],
  [qw/1 2 3/],
  [qw/a b c/],
);

...; # above code
is_deeply \@sorted, \@expected;
done_testing;