Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

A brief tutorial on Perl's native sorting facilities.

by BrowserUk (Pope)
on Feb 09, 2007 at 13:04 UTC ( #599204=perltutorial: print w/ replies, xml ) Need Help??

Simple sorting using sort

The basic method of sorting in Perl is to use the built in sort function.

  1. my @sortedAlpha = sort @alphaData;

    This does pretty much exactly what you'd expect. Takes an array(*) of data, orders it ascending (smallest first) according the ordinal (ASCII**) values of the characters in the strings:

    print for sort qw[ 12 a123 a122 A123 B123 Ab123 aB123 456 1A23 1a23 ] +;; 12 ## ord('1') == 49, ord('2') == 50 1A23 ## ord('A') == 65 so this comes after. 1a23 ## ord('a') == 97 " 456 ## ord('4') == 52 " A123 ## ord('A') == 65, ord('1') == 49 " Ab123 ## ord('b') == 98 " B123 ## etc. a122 a123 aB123

    *actually a list, but ignore that for now.

    **if your data is unicode, then the unicode ordinal values are used.

  2. my @reversedSordedAlpha = sort{ $b cmp $a } @alphaData;

    Here we want the data ordered in descending (largest first) sequence, so we have(*) to use code block to alter the default ordering.

    The { $b cmp $a } part of that tells sort that we wish to perform the ordering ourselves instead of using the default as we did in 1 above (which is equivalent to { $a cmp $b }). This says that for each pair of values in the input, Perl passes them to us (as $a and $b), and we perform a comparison and return

    • -1 if $a is less than $b
    • 1 if $a is greater than $b
    • 0 if $a equals $b

    With this information, sort can correctly do what it needs to do to reorder the input appropriately.

    By using the built-in cmp operator that is specifically designed for comparing strings and producing these values, we achieve the result we are after.

    Supplying the arguments $a and $b to the function in reverse order has the effect of reversing the sort.

    However, if we use cmp on numeric data, we do not get the effect we want:

    print for sort{ $b cmp $a } qw[ 1 10 100 2 20 21 3 300 ];; 300 3 21 20 2 100 10 1

    For numeric data we need to use the other built-in comparison operator <=>.

    *we can also use reverse, and that may actually be quicker, but this is a tutorial and this way demonstrates the point I wish to make.

  3. my @reverseSortedNumbers = sort { $b <=> $a } @numbers;

    Using <=> produces the desired result.

    print for sort{ $b <=> $a } qw[ 1 10 100 2 20 21 3 300 ]; 300 100 21 20 10 3 2 1

    The difference is that <=> compares the (binary) numerical value of its arguments, instead of the bytewise string comparisons of the ASCII representation that cmp does.

  4. my @sortedNumbers = sort{ $a <=> $b } @numbers;

    And for an ascending numerical sort, we just pass the parameters to <=> in the 'right' order.

How sort actually works internally doesn't really matter. What does matter is that being built-in to the language, it understands Perl's internals, is always available and about as fast as you are likely to achieve.

So, sorting data is easy, when you want to sort according to the entire value of each element of the array or list. It gets a little more complex when you want to sort the elements by a sub field of each element.

For example, say you have a set of ids (A123 B421 C987 etc.) and you want to order them by just the numeric part, then you need to extract that part before supplying it to the appropriate comparison function:

print for sort{ substr( $a, 1 ) <=> substr( $b, 1 ) } qw[ A473 B659 C123 D222 E001 ];; E001 C123 D222 A473 B659

This works fine, but each element will be passed to the comparison block multiple times, and that means we are extracting the sort field from each element multiple times, which can slow things down. For more complex cases, (eg. data consisting of dates), this could be significant. The purposes of the "advanced sorting" mechanisms is to reduce this slowdown by performing the extraction of the significant data from each input element once only.

The ST

One mechanism, and possibly the simplest to understand, is merlyn's ST (Schwartzian Transform). This works by pre-processing the elements to extract the fields, and packages them into anonymous arrays. The list of anonymous arrays are then sorted according to the extracted field. And finally, the original elements are recovered from the list of sorted anonymous arrays and stored into the sorted array.

## Build an array of anonymous arrays, ## each of which contains the sort field and the original element. @anons = map{ [ substr( $_, 1 ) , $_ ] } qw[ A473 B659 C123 D222 E001 +];; print Dumper \@anons;; $VAR1 = [ ['473','A473'],['659','B659'],['123','C123'], ['222','D222'],['001','E001'] ]; ## Now sort the anonymous arrays ## by comparing the extracted fields. @sortedAnons = sort{ $a->[ 0 ] <=> $b->[ 0 ] } @anons;; print Dumper \@sortedAnons;; $VAR1 = [ ['001','E001'],[123,'C123'],[222,'D222'], [473,'A473'],[659,'B659'] ]; ## Finally, build the required sorted array ## by extracting the original elements discarding the sort fields. @sorted = map{ $_->[ 1 ] } @sortedAnons;; print Dumper \@sorted;; $VAR1 = ['E001','C123','D222','A473','B659'];

This is quite simple to follow and can be coded in a more compact form, by combining the 3 steps into a single statement and doing away with the intermediate arrays:

@sorted = map{ $_->[1] } sort{ $a->[0] <=> $b->[0] } map{ [ substr( $_, 1 ), $_ ] } qw[ A473 B659 C123 D222 E001 ];; print Dumper \@sorted;; $VAR1 = ['E001','C123','D222','A473','B659'];

This is identical to the previous example, but more compact. It can also be formatted as a single line, though that will usually mean that it extends beyond the boundary at which PM does its dumb wrapping. It can also be laid out in several different ways to that I've shown, but I find that this makes the three significant steps of the algorithm clearly delineated, by indenting the contents of the code blocks just as you would for any other block of code. Eg. The body of if and while statements etc. I like this consistency.

The efficiency of the ST comes from only performing the extractions of the field data once. Indexing the anonymous arrays is very efficient and so the sorting and reassembly doesn't costs much extra. It also extends to sorting multiple fields in an obvious way:

print for map{ $_->[2] } sort{ $a->[0] <=> $b->[0] || $a->[1] cmp $b->[1] } map{ [ substr( $_, 1 ), substr( $_, 0, 1 ), $_ ] } qw[ A473 B437 B659 C659 C123 D123 D222 E222 E001 A001 ];; A001 E001 C123 D123 D222 E222 B437 A473 B659 C659

Here we've ordered the data according to the numeric field as before, but this time we've used the alpha field to 'tie-break' values when the numeric values are the same. It's easy to see how this can be further extended to handle as many fields of any type we need. This simple, obvious extension mechanism is the great strength of the ST.

The caveats

The downside of the ST is that for large datasets, the creation and destruction of all the small anonymous arrays can itself prove to be fairly expensive of time and memory.

It's also the case that calling back into Perl code via the sort comparison block imposes a significant time cost. (Don't worry about this for the simple cases of sort{ $a <=> } ... and sort{ $b cmp $a } shown above, as Perl has optimisations to recognise these simple cases, and it doesn't actually do a callback at all).

But for more complex sorting, these callbacks are expensive, and if you can avoid them, it will save some considerable time.

The GRT

This is where the (Guttman Rosler Transform) comes in. The basic idea here is that instead of building an anonymous array in the pre-processing stage, we prepend the field data to the front of the string; sort the strings; then strip the bit we stuck on the front back off.

Going back to the simpler example of a field sort above, we can construct the GRT as follows:

print for map{ ## Chop off the bit we added. substr( $_, 3 ) } sort map{ ## Note: No comparison block callback. ## Extract the field as before, but concatenate it with the origin +al element ## instead of building an anonymous array containing both elements +. substr( $_, 1 ) . $_ } qw[ A473 B659 C123 D222 E001 ];; E001 C123 D222 A473 B659
A cheat

This is actually something of a cheat of a GRT. It only works because in my carefully constructed example data, the numeric fields all have the same number of digits, with smaller values having leading zeros. Whilst this works fine, and makes the algorithm easy to follow (try adding print statements inside the code blocks to follow what is going on), real life data is rarely so accommodating. Whilst you could use sprintf to add leading zeros and so make your ascii encoded numeric fields sort correctly using the string comparisons (cmp), it turns out that there is a better (faster) way.

That way is to use pack to convert the numeric fields into binary values that will sort correctly using a string comparison function. It is convenient that binary encode integers (NOTE:In 'network' format only. That is 'N'&'n' *NOT* 'V'&'v') will sort correctly using a string comparison function. As will floating point data in IEEE formats (the format used internally by Perl on most but not all systems).

So, using pack, the previous example becomes:

print for map{ unpack 'x[N] A*', $_ } sort map{ pack 'N A*', substr( $_, 1 ), $_ } qw[ A473 B659 C123 D222 E001 ];; E001 C123 D222 A473 B659

That may not look so very different from the previous version, but the big advantage is that it will handle any integer values correctly, whereas with the previous version, you need to know how big the largest numeric field is, so that you can add the correct number of leading zeroes.

It also trivially extends to handle the two fields example shown above for the ST:

print for map{ unpack 'x[NA1]A*', $_ } sort map{ pack 'NA1 A*', substr( $_, 1 ), substr( $_, 0, 1 ), $_ } qw[ A473 B437 B659 C659 C123 D123 D222 E222 E001 A001 ]; A001 E001 C123 D123 D222 E222 B437 A473 B659 C659

The pattern

Hopefully, the pattern is becoming obvious. Use pack with appropriate templates 'N', 'n', 'd' etc. to prepend the sort field data to the strings in the order or precedence. Then use unpack and the same template as you used for the sort fields, but wrapped in 'x[...]' to strip the prefix off and recover the original elements.

A worked example

This following is one possible solution to sort array by date:

#! Perl -slw use strict; my %months = ( FY => 0, Jan => 1, Feb => 2, Mar => 3, Apr => 4, May => 5, Jun => 6, Jul => 7, Aug => 8, Sep => 9, Oct => 10, Nov => 11, Dec => 12, ); print for map{ unpack 'x[nn]A*', $_ } sort map { my( $alpha, $num ) = m[^(\S+?)\s*(\d+)$]; $num += 2000 if $num <= 49; $num += 1900 if $num <= 99; pack 'nnA*', $num, $months{ $alpha }, $_; } <DATA>; __DATA__ Apr 2006 FY05 FY98 FY04 Dec 2007 Jan 1997 Jan 1998 Dec 1998

Output:

C:\test>junk Jan 1997 FY98 Jan 1998 Dec 1998 FY04 FY05 Apr 2006 Dec 2007

Further reading

  1. Schwartzian Transform
  2. Advanced Sorting - GRT - Guttman Rosler Transform
  3. Choosing the right sort (Or: WUDsamatter?)
  4. fast, flexible, stable sort
  5. Re: Sort on Number Embedded in String
  6. Re: Sort on Number Embedded in String
  7. Resorting to Sorting

Updated with many corrections as suggested by planetscape, jdporter, holli, blazar, chromatic & shmem. Many thanks to all, including anyone I forgot to mention.

Comment on A brief tutorial on Perl's native sorting facilities.
Select or Download Code
Re: A brief tutorial on Perl's native sorting facilities.
by OfficeLinebacker (Chaplain) on Feb 16, 2007 at 21:48 UTC
    Hi. Great article. I like it a lot.

    I notice you wrote "It can also be formatted as a single line, though that will usually mean that it extends beyond the boundary at which PM does its dumb wrapping."

    AFAIK, line wrapping is controlled by a set of user-defined options on PM. I posted code which likely wrapped for other people who either like shorter lines or don't bother to change their settings. I noted in the post what my settings are. No one complained. :)

    Have a great weekend.


    I like computer programming because it's like Legos for the mind.
Re: A brief tutorial on Perl's native sorting facilities.
by teun-arno (Initiate) on Nov 21, 2008 at 23:02 UTC
    This is a great tutorial. Special the code with Data::Dumper. This makes clear how map and sort interact. Just a minor. The code will not run as displayed. So I added a runnable example :
    use Data::Dumper ## Build an array of anonymous arrays, ## each of which contains the sort field and the original element. @anons = map{ [ substr( $_, 1 ) , $_ ] } qw[ A473 B659 C123 D222 E0 +01 ];; my $dd=Data::Dumper->new([\@anons],[ qw(anons) ] )->Indent(2)->Quote +keys(0)->Dump; print $dd; print '-' x 40 , "\n"; ## Now sort the anonymous arrays ## by comparing the extracted fields. @sortedAnons = sort{ $a->[ 0 ] <=> $b->[ 0 ] } @anons;; my $dd=Data::Dumper->new([\@sortedAnons],[ qw(sortedAnons) ] )->Inde +nt(2)->Quotekeys(0)->Dump; print $dd; print '-' x 40 , "\n"; ## Finally, build the required sorted array ## by extracting the original elements discarding the sort fields. @sorted = map{ $_->[ 1 ] } @sortedAnons;; my $dd=Data::Dumper->new([\@sorted],[ qw(sorted) ] )->Indent(2)->Quo +tekeys(0)->Dump; print $dd; print '-' x 40 , "\n"; The above code will show : $anons = [ [ '473', 'A473' ], [ '659', 'B659' ], [ '123', 'C123' ], [ '222', 'D222' ], [ '001', 'E001' ] ]; ---------------------------------------- $sortedAnons = [ [ '001', 'E001' ], [ 123, 'C123' ], [ 222, 'D222' ], [ 473, 'A473' ], [ 659, 'B659' ] ]; ---------------------------------------- $sorted = [ 'E001', 'C123', 'D222', 'A473', 'B659', ]; ----------------------------------------

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perltutorial [id://599204]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (6)
As of 2014-12-19 01:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (70 votes), past polls