Section 9.1. Review of Sorting


9.1. Review of Sorting

Perl's built-in sort operator sorts text strings in their natural text order, by default.[*] This is fine if we want to sort text strings:

[*] My friends call that the "ASCIIbetical" ordering. Normally, modern Perl doesn't use ASCII; instead, it uses a default sort order, depending on the current locale and character set. See the perllocale (not perllocal!) manpage.

 my @sorted = sort qw(Gilligan Skipper Professor Ginger Mary_Ann); 

but gets pretty messy when we want to sort numbers:

 my @wrongly_sorted = sort 1, 2, 4, 8, 16, 32; 

The resulting list is 1, 16, 2, 32, 4, 8. Why didn't sort order these properly? It treats each item as a string and sorts them in string order. Any string that begins with 3 sorts before any string that begins with 4.

If we don't want the default sorting order, we don't need to write an entire sorting algorithm, which is good news since Perl already has a good one of those. But no matter what sorting algorithm we use, at some point we have to look at item A and item B and decide which one comes first. That's the part we'll write: code to handle just two items. Perl will do the rest.

By default, as Perl orders the items, it uses a string comparison. We can specify a new comparison using a sort block that we place between the sort keyword and the list of things to sort.[] Within the sort block, $a and $b stand in for two of the items sort will compare. If were sorting numbers, then $a and $b will be two numbers from our list.

[] We can also used a name subroutine that sort invokes for each comparison.

The sort block must return a coded value to indicate the sort order. If $a comes before $b in our desired sorting order, it should return -1; it should return +1 if $b comes before $a; if the order doesn't matter, it should return 0. The order might not matter, for example, if it's a case-insensitive sort comparing "FRED" to "Fred", or if it's a numeric sort comparing 42 to 42.[*]

[*] Actually, we can use any negative or positive number in place of -1 and +1, respectively. Recent Perl versions include a default sorting engine that is stable, so zero returns from the sort block cause the relative ordering of $a and $b to reflect their order in the original list. Older versions of Perl didn't guarantee such stability, and a future version might not use a stable sort, so don't rely on it.

For example, to sort those numbers in their proper order, we can use a sort block comparing $a and $b, like so:

 my @numerically_sorted = sort {   if ($a < $b)    { -1 }   elsif ($a > $b) { +1 }   else            {  0 } } 1, 2, 4, 8, 16, 32; 

Now we have a proper numeric comparison, so we have a proper numeric sort. Of course, this is far too much typing, so we can use the spaceship operator instead:

 my @numerically_sorted = sort { $a <=> $b } 1, 2, 4, 8, 16, 32; 

The spaceship operator returns -1, 0, and +1, according to the rules we laid out. A descending sort is simple in Perl:[]

] As of version 5.8.6, Perl recognizes the reverse sort and does it without generating the temporary, intermediate list.

 my @numerically_descending =     reverse sort { $a <=> $b } 1, 2, 4, 8, 16, 32; 

But there is more than one way to do it. The spaceship operator is nearsighted; and can't see which one of its parameters comes from $a and which from $b; it sees only which value is to its left and which is to its right. If we reverse the position of $a and $b, the spaceship will sort everything in the opposite order:

 my @numerically_descending =     sort { $b <=> $a } 1, 2, 4, 8, 16, 32; 

In every place the previous sort expression returned -1, this expression returns +1, and vice versa. Thus, the sort is in the opposite order, and so it doesn't need a reverse. It's also easy to remember because if $a is to the left of $b, we get out the lower items first, just like a and b would be in the resulting list.

Which way is better? When should we use a reverse sort, and when should we switch $a and $b? Well, in most cases it shouldn't matter much for efficiency, so it's probably best to optimize for clarity and use reverse. For a more complex comparison, however, a single reverse may not be up to the task.

Like the spaceship operator, we can indicate a string sort with cmp, although this is rarely used alone because it is the default comparison. The cmp operator is most often used in more complex comparisons, as we'll show shortly.




Intermediate Perl
Intermediate Perl
ISBN: 0596102062
EAN: 2147483647
Year: N/A
Pages: 238

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net