Perl: Sort List, Matrix, Object

Perm URL with updates: http://xahlee.info/perl/perl_sort.html

This page shows you how to sort in Perl

here's a example of sort (Perl 5.14):

#-*- coding: utf-8 -*-
# perl

# sort a list

@li = (1,9,2,3);

@li2 = sort {$a <=> $b} @li; # original list is not changed

print join(' ', @li2); # 1 2 3 9

In Perl, sort is a function. It returns the sorted result as another list.

“sort” takes the form sort {…} @myList. Inside the enclosing braces is the body of the ordering function, where variables 「$a」 and 「$b」 inside are predefined by the language to represent two elements in the list. The operator <=> returns -1 if left operand is less than the right operand. If equal, it returns 0, else 1. It is equivalent to Python's “cmp” function.

Another form of sort is sort orderFunctionName @list, which uses a function name in place of the comparison block. The function should have 2 parameters, and return one of {-1, 0, 1}.

Compare as Number or as String

Perl has 2 comparison operators.

  • ‹x› <=> ‹y› compare ‹x› ‹y› as numbers.
  • ‹x› cmp ‹y› compare ‹x› ‹y› as strings.

Example:

# -*- coding: utf-8 -*-
# perl

print "3" <=> "20"; # prints -1

print "\n";

print "3" cmp "20"; # prints 1

In Perl, numbers and strings are mutually automatically converted if needed.

Sort Matrix

# -*- coding: utf-8 -*-
# perl

# sort a matrix

use Data::Dumper;
use strict;

my @li1 = ([2,6],[1,3],[5,4]);

my @li2 = sort { $a->[1] <=> $b->[1] } @li1;

print Dumper(\@li2);            #  [[1, 3], [5, 4], [2, 6]]

The ([2,6],[1,3],[5,4]) is the syntax for nested list. The square brackets inside creates array references.

The $a->[1] is the syntax to get the element of a array reference.

The \@li2 in Dumper(\@li2) gets the reference to the array @li2.

Reverse Sort Order

To reverse sort order, all you have to do is to reverse the placement of $a and $b in your comparison. Example: sort {$b <=> $a} @li

Or, you can use the reverse function afterward, if you don't mind doing extra computation.

# -*- coding: utf-8 -*-
# perl

use Data::Dumper;

@aa = (3, 4, 5);

@bb = reverse(@aa);

print Dumper(\@bb);

Sort Complex Objects

Here's a more complex example of sort.

Suppose you have a list of strings.

'my283.jpg'
'my23i.jpg'
'web7-s.jpg'
'fris88large.jpg'
…

You want to sort them by the number embedded in them.

You need to define a ordering function, and pass it to sort. The function should takes two strings, and compare the integer inside the string. Here's the solution:

#-*- coding: utf-8 -*-
#  perl

@li = (
'my283.jpg',
'my23i.jpg',
'web7-s.jpg',
'fris88large.jpg',
);

# sorts a list of strings by their embedded number

@li2 = sort { ($a =~ m/(\d+)/)[0] <=> ($b =~ m/(\d+)/)[0]} @li;

print join(' ', @li2);  # prints web7-s.jpg my23i.jpg fris88large.jpg my283.jpg

decorate-sort-dedecorate, Schwartzian transform

Normally, the key for comparison is computed 2 or more times for each element.

Here's a more efficient way, called decorate-sort-dedecorate (aka Schwartzian transform).

# -*- coding: utf-8 -*-
# perl

# sort a array of string, by comparing the number part inside the string

@li = ('my283.jpg','my23i.jpg','web7-s.jpg','fris88large.jpg');

# this is “decorate-sort-dedecorate”, aka Schwartzian transform
@li2 = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [ $_, ($_=~m/(\d+)/)[0] ] } @li;
#          ↑ take item               ↑ sort            ↑ create list of pairs [item,key]

use Data::Dumper;
print Dumper(\@li2); # ('web7-s.jpg', 'my23i.jpg', 'fris88large.jpg', 'my283.jpg')

In the above Perl code:

  • the map { [ $_, ($_=~m/(\d+)/)[0] ] } @li; generates a temp array. Each element is a pair, item & key.
  • Then, sort is applied to the temp array.
  • Then, another map map { $_->[0] } … gets the items of the original list.

In this way, the cost to compute the same key multiple times is avoided. This method is good when computing the key is expensive.

perldoc -f sort

General Function to Sort Matrix

See: Perl: General Function for Sorting Matrix

Popular posts from this blog

11 Years of Writing About Emacs

does md5 creates more randomness?

Google Code shutting down, future of ErgoEmacs