Sorting data with perl - Part Two

[KevinADC]

Introduction

In part one we discussed the default sort function. In part two we will discuss more advanced techniques you can use to sort data. Some of the techniques might introduce unfamiliar methods or syntax to a less experienced perl coder. I will post links to online resources you can read if necessary. Experienced perl coders might find nothing new or useful contained in this article.

Short Review

In part one I showed you some very basic syntax you can use to sort data:

@sorted = sort (@array); # default lexical ascending order sort
@sorted = reverse sort @array; # default lexical sort in reverse/descending order
@sorted = sort {$a cmp $b} @array; # same as first example
@sorted = sort {$b cmp $a} @array; # same as second example
 

There is nothing wrong with using any of them if the data can be sorted using one of these "simple" sorts. In fact, the first example is probably the most efficient way of sorting data using perl (default ascending lexical sort). The problem is that data is rarely formatted such that you can use the default sort and get good results. But of course you can use perl to process the data to get it into a format that can be sorted. You have two options: process the data while sorting it or process the data before sorting it. Which method to use depends on your data and how much processing you need to do to sort it. Only you can determine which sorting method works best for your particular data.

Processing Data While Sorting

If you don't have much data to sort or little processing to do this can be a good option. It takes less planning and experience to get working and is generally efficient enough for most applications. For the first example we will use a list of names:

my @names = qw(Jim JANE fred Andrew Chris albert sally Martha);

To sort them alphabetically we need to convert them to all upper or lower case letters to avoid lexical sorting of upper case characters before lower case characters. Here is one way:

my @sorted = sort {lc $a cmp lc $b} @names;

We used a code block {} and perls lc (lower-case) operator to process the data while sorting it.

The sorted list:

albert
Andrew
Chris
fred
JANE
Jim
Martha
sally

Note that the data has not been changed, only the order. It is still in the same format of mixed case characters. The data is assigned to $a or $b and converted to lower case only during the sort comparison. What this means is that some of the data will be converted to lower case characters more than one time during the sort. This can have a big impact on how long it takes to sort data if the processing is slow. In this example, using the lc operator is marginal as far as overall performance goes. Even if it were a list of a million names it should still go pretty fast. But if you needed to use regular expressions or sorting by different fields or sorting references to data it can pay big dividends to pre-process the data before sorting.

Another way is to use a subroutine instead of a code block:

my @sorted = sort lowercase @names;
 
sub lowercase {
   return lc $a cmp lc $b;
}
 

Perl treats a subroutine called by the sort function differently than other subroutines. You do not pass the data being sorted to the subroutine via @_, perl will do that internally and assign the data to $a and $b. Do not declare $a and $b with "my" even when using the "strict" pragma. They are package globals so your program will not complain about $a and $b needing to be declared with "my". And don't change or modify $a and $b. They are actually references back to the source data, so changing them could produce bizarre behavior.

You can give sorting subroutines meaningful names so it's function is understood i.e.: by_age by_date by_name by_number. Generally I find using a code block easiest for simple sorts like the previous examples and reserve using a subroutine for more complex sorts. Assume we have an array of hashes; the keys are first_name, last_name, and age.

 
my @sorted = sort by_name_and_age @array_of_hashes;
 
sub by_name_and_age {
    return    $a->{last_name} cmp $b->{last_name}
              || $a->{first_name} cmp $b->{first_name} 
              || $b->{age} <=> $a->{age};
}
 

Here we introduce the || (or) operator. When perl is sorting data it returns -1 if $a comes before $b, 0 if they are the same, and 1 if $a comes after $b. If any of the comparisons returns 0, perl goes to the next comparison because of the || operator. If a comparison returns -1 or 1, perl stops comparing. If all of the comparisons return 0, the first bit of data evaluated will be listed first. Note that the age key is sorted in descending order. You can mix ascending and descending comparisons in the same sort. If the first and last names are the same, the oldest person will be listed first. If you are unfamiliar with complex data like was assumed in the last example, an array of hashes, here is a link to a tutorial on the perldoc website: Complex Data Structures.

Part three of Sorting Data with Perl will discuss methods of sorting after processing.

This article is protected under the Creative Commons License.

[KevinADC]

Comments, corrections, discussions about this article and perls sort function are welcome. Post general perl questions in the perl forum.