python 3: sorting with a comparison function

Kay Schluehr kay.schluehr at gmx.net
Fri Oct 10 20:03:40 CEST 2008


On 10 Okt., 19:22, prueba... at latinmail.com wrote:
> On Oct 10, 8:35 am, Kay Schluehr <kay.schlu... at gmx.net> wrote:
>
> > On 9 Okt., 22:36, bearophileH... at lycos.com wrote:
>
> > > Yes, that's a wonderful thing, because from the code I see around
> > > 99.9% of people see the cmp and just use it, totally ignoring the
> > > presence of the 'key' argument, that allows better and shorter
> > > solutions of the sorting problem.
>
> > Me too because I don't get this:
>
> > "key specifies a function of one argument that is used to extract a
> > comparison key from each list element: key=str.lower. The default
> > value is None."
>
> > Kay
>
> Don't know if further explanation is needed, but here is the deal:
>
> cmp is a function that receives two values and you return -1, 0 or 1
> depending if the first is smaller, equal or bigger. 99% of the time
> you will do some operation on the values that come in and then do a if
> statement with ">" or "<" and return -1,0,1.
>
> key is a function that receives one value and you return the value
> that you would normally compare against.
>
> Let me show an example:
>
> >>> data=[(4,'v'),(2,'x'),(1,'a')]
> >>> sorted(data)
>
> [(1, 'a'), (2, 'x'), (4, 'v')]
>
> OK, we sorted the data, but What if we want to sort by the letter
> instead of the number? Let's use cmp:
>
> >>> def comp(x, y):
>
>       key_of_x=x[1]
>       key_of_y=y[1]
>       if key_of_x < key_of_y:
>         return -1
>       elif key_of_x > key_of_y:
>         return 1
>       else:
>         return 0 #key_of_x == key_of_y
>
> >>> sorted(data,cmp=comp)
>
> [(1, 'a'), (4, 'v'), (2, 'x')]
>
> Very well, so how do we do this using key?
>
> >>> def keyfunc(x):
>
>       key_of_x=x[1]
>       return key_of_x
>
> >>> sorted(data,key=keyfunc)
>
> [(1, 'a'), (4, 'v'), (2, 'x')]
>
> Same output. Very good.
>
> (Of course a smart python developer would use the operator module so
> he doesn't even have to write keyfunc but this was just an example)
>
> In summary to transform most cmp functions to a key function you just
> take the code that calculates the first value to be compared and leave
> out the rest of the logic.
>
> Hope that was helpful.

Yes, thanks a lot. In essence the "key" is a function that maps each
list element onto a value of a type for which a known order is defined
e.g. an integer. Applying sorted() sorts the list elements according
to the list of those values.

Sometimes it helps when people just make clear how they use technical
terms instead of invoking vague associations.



More information about the Python-list mailing list