Sorting multiple arrays

[Kempie]

Hi,

I have several arrays of the same length where each indexed element is related i.e. $array_a[0] is linked to $array_b[0] etc. and the same for all other elements / arrays.

One of the arrays is numeric - I want to sort this array, but perform the same sort on the other arrays so that the elements remain lined up

e.g. 

array_a = (fred,bob,john,peter)
array_b = (2,1,4,3)

After sorting numerically on array_b

array_a = (bob,fred,peter,john)
array_b = (1,2,3,4)

Any suggestions for a simple way to this would be appreciated. If I can't do it with arrays like this, should I change the data structure to something else?

Hoping you can help,

Andy

[dragonchild]

You have two options:
1. Change your data structure to an array of hashes.
2. Sort the indices, then apply the sorted indices as a slice to each array.
The first option is better because you end up with a better data structure.

my @values = (
    { name => 'fred', index => 2 },
    { name => 'bob', index => 1 },
    { name => 'john', index => 4 },
    { name => 'peter', index => 3 },
);

my @sorted_values = sort { $a->{index} <=> $b->{index} } @values;

If you wanted to take option 2 because, for instance, you cannot change the data structures in question, you could do something like:

my @sorted_indices = sort { $array_b[$a] <=> $array_b[$b] } 0 .. $#arr
+ay_b;

@array_a = @array_a[@sorted_indices];
@array_b = @array_b[@sorted_indices];

That, however, is much more fragile and depends a lot on you maintaining parallel data structures. The first option is much more robust and tolerant of change.

[dorward]

It sounds like you would be better off using a single array of hashrefs instead.

my @array = (
  { name => 'fred',  number => 2 },
  { name => 'bob',   number => 1 },
  { name => 'john',  number => 4 },
  { name => 'peter', number => 3 },
);

Then you can sort them like so:

@array = sort { $a->{number} <=> $b->{number} } @array;

[Roy Johnson]

What you have is essentially a hash. array_b is your keys, array_a is your values:

my %h;
@h{@array_b} = @array_a;
# Now you can sort however you want, and they're linked:
for (sort {$a <=> $b} keys %h) {
  print "$_: $h{$_}\n";
}

If array_b starts at zero and doesn't skip values, you can use an array similarly:

my @sorted_values;
@sorted_values[@array_b] = @array_a; # magically sorted!

If it skips some values (but doesn't range into absurdly high numbers) and/or doesn't start at zero, you can grep out the undefs (assuming you don't have valid undef values):

# same as above, then
@sorted_values = grep defined, @sorted_values;

[merlyn]

Use an array slice:

my @sorted_a = @array_a[sort { $array_b[$a] <=> $array_b[$b] } 0..$#ar
+ray_b];

[Codon]

This doesn't sort @array_b. The OP could then just numeric sort @array_b in a separate operation.

[merlyn]

Maybe I skimmed too fast, but I thought the sorting of array_b was only a logical sort to show how array_a needed to be reordered.

If that's not the case, saving the indicies and using them twice would do the trick:

my @indicies = sort { $array_b[$a] <=> $array_b[$b] } 0..$#array_b;
my @sorted_a = @array_a[@indicies];
my @sorted_b = @array_b[@indicies];

[keck]

Try using a hash of arrays or hash of hashes. Without more info it's not clear which is better for your application. This way you can sort the hash by keys or by a particular value, or whatever. if array_a is names, array_b is birth_order and array_c is salary (just for example) you could replace those arrays with a structure like this:

  # First make a hash to hold it all
  my %p = ();   # p is short for people so I can type less.

  #  bob, fred, peter and john are keys of %p, and refs to 
  # hashes we didn't predeclare.  This is what makes hashes 
  # of hashes (or arrays) so useful, they are easily 
  # populated from unknown data.

  $p{bob}{birth_order}   = 1;
  $p{fred}{birth_order}  = 2;
  $p{peter}{birth_order} = 3;
  $p{john}{birth_order}  = 4;

  $p{bob}{salary}   = 50000;
  $p{fred}{salary}  = 60000;
  $p{peter}{salary} = 70000;
  $p{john}{salary}  = 80000;
  
  # to sort by the people's names:
  for my $name ( sort keys %p ){
    # do something here
  }

  # to sort by the people's birth order:
  for my $name ( sort { $p{$a}{birth_order} <=> $p{$b}{birth_order} } 
+keys %p ) {
    print "$p{$name}{birth_order}, $name\n";
  }

I wrote out a bit of it long hand just to illustrate, but there are certainly better ways of creating these hashes.

[inman]

Using and array of arrays will allow the OP to sort the data by any part of the record.

use strict;
use warnings;
use Data::Dumper;

my @array_keys = (2,1,4,3);
my @array_values = ('fred','bob','john','peter');

my @aoa = sort {$a->[0] <=> $b->[0]} 
  map {[$array_keys[$_], $array_values[$_]]} 0..$#array_keys;

print Dumper(\@aoa);

[Codon]

merlyn had probably the most simple solution. I, however, like the creative solution. AoH or Hash based solutions are obvious. How's this for a unique method:

my @a = qw(fred bob john peter);
my @b =   ( 2, 1, 4, 3 );

my @a_sorted = @b_sorted = ();

push( @{ ($|-- ? \@b_sorted : \@a_sorted ) }, $_ ) for
    map  {           @$_           }
    sort {   $a->[1] <=> $b->[1]   }
    map  { [ $a[$_],     $b[$_]  ] } (0 .. $#b);

print " $a_sorted[$_]  => $b_sorted[$_] \n" for ( 0 .. $#b_sorted );

The one thing that I don't like about this is that it does not sort in place. It requires the creation of two new sorted arrays. :-(

[blazar]

I have several arrays of the same length where each indexed element is related i.e. $array_a[0] is linked to $array_b[0] etc. and the same for all other elements / arrays.

Then evidence suggests that the data contained in those array could be better organized in a more complex structure reflecting their internal logical relationships, e.g. a so called AoA or an AoH. For example you may have

#!/usr/bin/perl

use strict;
use warnings;
use Data::Dumper;

my @array=([2, 'fred'],
           [1, 'bob'],
           [4, 'john'],
           [3, 'peter']);

print Dumper [ sort {$a->[0] <=> $b->[0]} @array ];

__END__

=>

$VAR1 = [
          [
            1,
            'bob'
          ],
          [
            2,
            'fred'
          ],
          [
            3,
            'peter'
          ],
          [
            4,
            'john'
          ]
        ];

[Kempie]

Many many thanks, especially to Merlyn for the simple solution as reply #3 in this thread. I have used this and it works a treat.

I had wondered how you could extract the indices from a perl sort operation but could see a simple way to do it. My real example had 5 linked arrays and using Merlyns method does the job in 6 lines of code. It is in a user interface function, so I was not bothered about performance.

To all who suggested I use a Hash structure, I know that would probably have been right, but generating the simple linked arrays was easy from the previous data, but the hash would have been (a little) more tricky.

The actual application was building an AoA for GD::Graph

Once again, thankyou to all for your ideas and time

Andy