[Tutor] Sorting

[Tim Peters]

[posted & mailed]

[possibly Daniel Yoo -- hard to tell!]
> I believe that you can write a quick lambda expression to use
> with the python sort() routine that should work nicely.  Here's
> an example program that sorts lines based on the character on
> the 4 column:
>
> import sys
> from string import *
> lines = sys.stdin.readlines()
> lines.sort(lambda x,y: x[3] > y[3])
> for x in lines: print rstrip(x)

[Ben Beuchler]
> I have to admit, the ability to pass extra arguments to x.sort()
> confuses me.  Can you clarify a little what is happening in that
> lambda expression and how it talks sort into dealing with the
> fourth column instead of the first?

Part of the confusion may be <wink> that the example above is incorrect.

First do yourself a favor, and forget lambdas:  use ordinary named
functions.  They're easier to understand and more powerful.

Sorting works by comparing pairs of list elements.  If you don't want the
way Python compares elements by default, you can pass a function to
list.sort() that tells Python how to compare elements the way *you* want
them compared.  Such a function takes two arguments, the elements to be
compared.  Call them x and y.  The function should return -1 if x<y, 0 if
x==y, or 1 if x>y (this strange interface is inherited from the C language's
sorting routines).  list.sort() calls this function each time it needs to
compare a pair of elements.

If you don't pass an argument, the builtin function "cmp" is used by
default.  So the normal list.sort() is equivalent to (except quicker than):

def normal_compare(x, y):
    return cmp(x, y)

list.sort(normal_compare)

In turn, that's equivalent to list.sort(cmp) (putting a wrapper
"normal_compare" around cmp doesn't change what cmp does!).

If you want to sort in *reverse* order, one way to do it is

def reverse_normal_compare(x, y):
    return cmp(y, x)   # note the argument order is swapped

list.sort(reverse_normal_compare)

Another, trickier, way is:

def reverse_normal_compare(x, y):
    return -cmp(x, y)   # swaps +1 with -1, leaves 0 alone

But don't do either of those <wink>.  The best (simplest and by far fastest)
way to reverse sort is

list.sort()
list.reverse()

Once you understand how the "reverse sort" works, fancier applications are
just details piled on top of the same basic idea.  See Andrew Dalke's
excellent examples at

http://www.python.org/doc/howto/sorting/sorting.html