Sorting with Indices (Learning Perl Objects, References & Modules)

7.2. Sorting with Indices

In the same way you used indices to solve a few problems with grep and map back in Chapter 5, you can also use indices with sort to get some interesting results. For example, let's sort the list of names from earlier:

my @sorted = sort qw(Gilligan Skipper Professor Ginger Mary_Ann);
print "@sorted\n";

which necessarily results in:

Gilligan Ginger Mary_Ann Professor Skipper

But what if you wanted to look at the original list and determine which element of the original list now appears as the first, second, third, and so on, element of the sorted list? For example, Ginger is the second element of the sorted list and was the fourth element of the original list. How do you determine that the second element of the final list was the fourth element of the original list?

Well, you can apply a bit of indirection. Let's not sort the actual names but rather the indices of each name:

my @input = qw(Gilligan Skipper Professor Ginger Mary_Ann);
my @sorted_positions = sort { $input[$a] cmp $input[$b] } 0..$#input;
print "@sorted_positions\n";

This prints 0 3 4 2 1, which means that the first element of the sorted list is element 0 of the original list, Gilligan. The second element of the sorted list is element 3 of the original list, which is Ginger, and so on. Now you can rank information rather than just move the names around.

Actually, you have the inverse of the rank. You still don't know for a given name in the original list about which position it occupies in the output list. But with a bit more magic, you can get there as well:

my @input = qw(Gilligan Skipper Professor Ginger Mary_Ann);
my @sorted_positions = sort { $input[$a] cmp $input[$b] } 0..$#input;
my @ranks;
@ranks[@sorted_positions] = (0..$#sorted_positions);
print "@ranks\n";

The code prints 0 4 3 1 2. This means that Gilligan is position 0 in the output list, Skipper is position 4, Professor is position 2, and so on. The positions here are 0-based, so add 1 to get "human" ordinal values. One way to cheat is to use 1..@sorted_positions instead of 0..$#sorted_positions, so a way to dump it all out might look like:

my @input = qw(Gilligan Skipper Professor Ginger Mary_Ann);
my @sorted_positions = sort { $input[$a] cmp $input[$b] } 0..$#input;
my @ranks;
@ranks[@sorted_positions] = (1..@sorted_positions);
for (0..$#ranks) {
  print "$input[$_] sorts into position $ranks[$_]\n";
}

This results in:

Gilligan sorts into position 1
Skipper sorts into position 5
Professor sorts into position 4
Ginger sorts into position 2
Mary_Ann sorts into position 3


7. Practical Reference Tricks		7.3. Sorting Efficiently