Q: sort's key and cmp parameters

kj no.email at please.post
Thu Oct 1 19:08:33 CEST 2009



Challenge: to come up with a sorting task that cannot be achieved
by passing to the sort method (or sorted function) suitable values
for its key and reverse parameters, but instead *require* giving
a value to its cmp parameter.

For example,

from random import random
scrambled = some_list.sort(cmp=lambda x, y: cmp(random(), 0.5))

can be achieved (to a very good approximation at least) with

scrambled = some_list.sort(key=lambda x: random())

Is there a real-life sorting task that requires (or is far more
efficient with) cmp and can't be easily achieved with key and
reverse?

Many thanks in advance,

G.

P.S. I guess that, if sort is going to produce a non-trivial,
*consistent* order, a function CMP passed as the value of its cmp
parameter must satisfy the following properties:

0. CMP(x, y) must be non-zero for some elements x, y of the list; 
1. anti-symmetry: sign(CMP(x, y)) must be equal to -sign(CMP(y, x));
2. transitivity: if sign(CMP(x, y)) equals sign(CMP(y, z)), then
   sign(CMP(x, z)) must be equal to sign(CMP(x, y)).

In (1) and (2), sign() stands for the function

            -1 if x  < 0
  sign(x) =  0 if x == 0
             1 if x  > 0

I suppose that all bets are off if these properties are not satisfied,
though the documentation does not make this entirely clear, as far
as I can tell.  (If I'm wrong about this alleged omission, please
point me to the part of the docs that I missed.)



More information about the Python-list mailing list