Code snippet: Natural string sorting

[Matteo Dell'Amico]

C. Barnes wrote:
> Summary:
> 
> Sorts strings in a way that seems natural to humans. 
> If the
> strings contain integers, then the integers are
> ordered
> numerically.  For example, sorts ['Team 11', 'Team 3',
> 'Team 1']
> into the order ['Team 1', 'Team 3', 'Team 11'].
[snip]

Nice. Can be written (and, hopefully, made a bit more efficient) using 
the Decorate-Sort-Undecorate pattern too:

import re

_expr = re.compile(r'(\d+|\D+)')

def try_int(s):
     if s.isdigit():
         return int(s)
     else:
         return s

def nat_key(s):
     return [try_int(e) for e in _expr.findall(s)]

def nat_nocase_key(s):
     return nat_key(s.lower())

def decsorted(seq, key):
     decorated = [(key(item), item) for item in seq]
     decorated.sort()
     return [item for k, item in decorated]

Then you could use decsorted(seq, nat_key) or decsorted(seq, 
nat_nocase_key).

If someone is found of one-liners, he can just write nat_key as

def nat_key(s):
     return map(lambda s: s.isdigit() and int(s) or s, _expr.findall(s))

Note that 2.4's sorted() and list.sort() will have built-in support for 
decorate-sort-undecorate, so you'll just have to throw nat_key or 
nat_nocase_key to them, with no need for decsorted.

-- 
Ciao,
Matteo