CODEWITHSUNDEEP
arraysperlsorting
jkshah
jkshah

Reputation: 11713

Sorting arrays with reference to a sorted array

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

Upvotes: 8

Views: 278

Answers (4)

mpapec
mpapec

Reputation: 50647

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

Upvotes: 10

salva
salva

Reputation: 10244

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;

Upvotes: 1

Hynek -Pichi- Vychodil
Hynek -Pichi- Vychodil

Reputation: 26121

All presented solutions shows sorting with O(NlogN) time complexity. There is a way how to do it without actual sorting so in O(N) time complexity.

sub custom_usort {
    my %h;
    @h{@_} = ();
    grep exists $h{$_}, ('one','two','three','four','five','six');
}

Edit:

If there can be multiple values in input, there is this solution:

sub custom_sort {
    my %h;
    $h{$_}++ for @_;
    no warnings 'uninitialized';
    map {($_) x $h{$_}} ('one','two','three','four','five','six');
}

Upvotes: 0

amon
amon

Reputation: 57640

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;

Upvotes: 4

Related Questions