How can I sort a Perl list in an arbitrary order?

Question

Hi Everyone,

I have a list of strings whose values come from a fixed set. I need to sort this list in an arbitrary order.

The order of the set is specified by another list of all possible strings, sorted in order in an array.

Here is an example:

my @all_possible_strings_in_order = ('name', 'street', 'city','state', 'postalcode');

my @list_that_needs_to_be_sorted = ('city', 'state', 'name');

I am working in perl. I figure my best bet is to automatically create a hash that associates strings with ordinal numbers, and then sort by reference to those ordinal numbers.

There are about 300 possible strings in the set. Typical lists will have 30 strings that need to be sorted. This isn't going to be called in a tight loop, but it can't be slow either. Automatically building the ordinal hash can't be done ahead of time due to the structure of the program.

I'm open for suggestions on better ways to do this. Thanks!

Edit: You guys are awesome. I can't hold my head up any more tonight, but tomorrow morning I'm going to take the time to really understand your suggestions... It's about time I became proficient with map() and grep().

Answer 1

Set up the association between strings and their respective positions with

my @all_possible_strings_in_order = qw/ name street city state postalcode /;

my %order = map +($order[$_] => $_), 0 .. $#all_possible_strings_in_order;

Now you can create a comparison function for use with Perl's sort operator:

sub by_order { $order{$a} <=> $order{$b} }

For example:

my @sorted = sort by_order qw/ city state name /;
print "@sorted\n";
# prints: name city state

Answer 2

Here's an idea that's fairly simple.

Take your first string from your unsorted list, search for it in your master list, find its index in the master list, then place it in a list, and keep track of the index.

Take your second string, find its index in the master list. if that index is greater than the first, place it in your new list behind the first, otherwise in front.

Keep this up for all remaining strings, maintaining a list of all the indices, so that you always know where to place the next string re the strings already sorted.

Hope this is clear enough to help.

John Doner

Answer 3

If you have Perl 5.10, you could use this (names shortened for clarity):

use feature 'state';

sub bylist {
  state %hash = map { $all_possible[$_] => $_ } 0 .. $#all_possible;
  $hash{$_[0]} cmp $hash{$_[1]};
}

my @sorted = sort bylist @list_to_sort;

The state keyword creates what in C is known as a static variable - it's local to the bylist subroutine, but it won't be reinitialized. That way, you don't have to set anything up beforehand, but don't have to recalculate the value every time you want to use it.

I believe there's a hack to get this to happen in older Perls, but I wouldn't use it. If you don't have 5.10, just use gbacon's idea that he shamelessly stole from my brain while I was typing this :P

Answer 4

The most naive way to do this would be to sort based on a comparison function, where the comparison function comp(a,b) = "which of a and b comes first in the master list?", if I understand correctly.

So yeah, your idea looks about right. If you have to do a lot of sorts between changes to @all_possible_strings_in_order, then you should build the whole map once. If the order list changes every sort, you may be able to gain some speed with some clever lazy search, but maybe not.

my %order;
my $i = 0;
foreach my $s (@all_possible_strings_in_order) {
    $order{$s} = $i++;
}

my @sorted = sort {$order{$a} <=> $order{$b}} @list_that_needs_to_be_sorted;

I imagine this should be quite fast.

Answer 5

A different approach (one that won't work if the list to be sorted can have duplicates that need to be preserved):

my %set;
@set{ @list_that_needs_to_be_sorted } = ();
my @sorted = grep exists $set{$_}, @all_possible_strings_in_order;

Answer 6

You can just go over the master list and push any element that occurs in the unsorted list onto the result list, while removing it from the unsorted list. If your unsorted list is short (from your example, I reckon about 5 elements), this should be faster and smaller than building hash tables each time (you said you couldn't do it once beforehand).

An optimization might be to make a trie from the unsorted list, but whether this is better is dependent on the size of each list.