sort the list

Nick Craig-Wood nick at craig-wood.com
Tue Nov 22 15:30:05 CET 2005


Daniel Schüle <uval at rz.uni-karlsruhe.de> wrote:
>  lst.sort(lambda x,y: cmp(x[1], y[1]))

Since no-one mentioned it and its a favourite of mine, you can use the
decorate-sort-undecorate method, or "Schwartzian Transform"

eg

lst = [[1,4],[3,9],[2,5],[3,2]]
# decorate - ie make a copy of each item with the key(s) first and the
# actual object last
L = [ (x[1],x) for x in lst ]
# sort
L.sort()
# undecorate
L = [ x[-1] for x in L ]

The Schwartzian transform is especially good when making the key is
expensive - it only needs to be done N times, wheras a typical sort
routine will call the cmp function N log N times.  Its expensive in
terms of memory though.

With python 2.4 you can wrap it up into one line if you want

[ x[-1] for x in sorted([ (x[1],x) for x in lst ]) ]

or even

[ x[-1] for x in sorted((x[1],x) for x in lst) ]

-- 
Nick Craig-Wood <nick at craig-wood.com> -- http://www.craig-wood.com/nick



More information about the Python-list mailing list