Sorting arrays with reference to a sorted array

Question

I have a reference array which contains all possible elements and is sorted in custom order different than alphanumeric sorting. For example,

@ref_array = ('one','two','three','four','five','six');

Now all input arrays need to be sorted based on order of reference array. Input array will always be subset of reference array.

@in1 = ('three','one','five');  # Input
@out1 = ('one','three','five'); # Desired Output

@in2 = ('six','five','four','three','two','one'); # Input
@out2 = ('one','two','three','four','five','six') # Desired Output

Answer 1

my %h = map { $ref_array[$_] => $_ } 0 .. $#ref_array;

my @out1 = @ref_array[ sort { $a <=> $b } @h{@in1} ];
my @out2 = @ref_array[ sort { $a <=> $b } @h{@in2} ];

%h holds key => val pairs like one => 0, two => 1, etc.

@h{@in1} is 2,0,4 hash slice which gets sorted, and array slice @ref_array[0,2,4] is one, three, five

Answer 2

This isn't that complicated.

Step 1, we need a mapping from your values to some key that Perl can sort, e.g. numbers. We can use the indices of the elements in your custom collation array, like:

my %custom_value = map { $ref_array[$_] => $_ } 0 .. $#ref_array;

Step 2, we do a Schwartzian Transform on your input with one of the above values as key:

my @out =
  map  { $_->[1] }
  sort { $a->[0] <=> $b->[0] }
  map  {[ $custom_value{$_} => $_ ]}
       @in;

Answer 3

For sorting using a small-integer key, radix sort is usually the faster solution with O(N) complexity:

use Sort::Key::Radix qw(ukeysort);

my @ref = ('one','two','three','four','five','six');
my %ref = map { $ref[$_] => $_ } 0..$#ref;

my @out = ukeysort { $ref{$_} } @in;

Or you can also use a cheap O(N) counting sort:

my %ref;
$ref{$_}++ for @in;
no warnings 'uninitialized';
my @out = map { ($_) x $ref{$_} } @ref;