sorting using a custom definition of “>” and “< ” in python

suppose I have a custom function such as

def greater(a, b):
if (a % b) % 2 == 0:
return 1
return 0

It defines how to compare two numbers and determine which is greater. In this case, if the function returns 1 a > b else, a < b. Can I use inbuilt <built-in function sorted> orto create a sorted array of numbers with respect to this definition?

If you're using Python 2.x, then that's easily achievable by using cmp, although you have to modify your function to return -1 instead of 0. Something like this:

def greater(a, b):
if (a % b) % 2 == 0:
return 1
return -1

x = [2,7,5,10,30,15]

print(sorted(x, cmp=greater))

But if you're using Python 3.x, then it gets a bit more complicated since cmp was removed. My best idea is to implement a class to hold the number and override the comparison operators __lt__ (less than) and __gt__ (greater than). Something like this:

class my_int(int):
def __lt__(a,b):
return (a % b) % 2 != 0
def __gt__(a,b):
return (a % b) % 2 == 0

x = [my_int(2),my_int(7),my_int(5),my_int(10),my_int(30),my_int(15)]

print (sorted(x))
• this is exactly what I was looking for! thanks I"m using python 2.7.2 – user5198 Jun 1 '12 at 0:40
• I still can't believe removal of cmp was deemed a good idea for 3.x... – Izkata Jun 1 '12 at 2:19
• @Izkata - Yeah a lot of the stuff done in the name of the all powerful Pythonic "only one way of doing things" just don't make sense to me. – System Down Jun 1 '12 at 4:13
• python3.2+ has functools.cmp_to_key which essentially defines that class for you given the cmp function. So you can do sorted(x, key=cmp_to_key(greater)) – zstewart Oct 27 '15 at 19:36

No.

Your function does not give consistent answers on how to sort numbers, because greater(x, y) != not greater(y, x) for some values of x and y. For example (3 % 4) % 2 == 1, and (4 % 3) % 2 == 1 also! This means that 3 > 4 AND 3 < 4, which is nonsense. If you convert it to a cmp-style function like @SystemDown suggests, you will get inconsistent results. For example:

>>> sorted(range(3, 6), cmp=greater)
[5, 4, 3]
>>> sorted(range(1, 6), cmp=greater)
[1, 4, 3, 5, 2]

Here 5 is smaller than 4 in one case but larger than 4 in another, using the same comparison function!

Even if your cmp function was self-consistent, I'd advice against using it in any way or form, like using the cmp_to_key function suggested by @zstewart, because a cmp function is slower harder to read and debug than an equivalent key function.

Using key functions, the function gets called only once per item to be sorted, so if you have a list of 1 million items, it gets called a million times. Then the sorting proceeds and compares the return values of the key function n*log(n) times, on average. For a list of 1 million elements, that's 13.8 million times.

If you use a cmp function instead, it gets called once for each of those n*log(n) comparisons! Again, that's 13.8 million times if the list contains 1 million elements. If you use cmp_to_key, you'll get an additional overhead of instantiating 1 million instances of a helper class.

I tested with a list of 1 million random integers using these functions, which accomplish the same thing:

def cmp_func(a, b):
if a > b:
return -1
elif a < b:
return 1
else:
return 0

def key_func(x):
return -x

Sorting with key_func took 1.35 s, while using cmp_func required 2.43 s.

So to answer the implicit question of @lzkata, it was deemed a good idea to remove the cmp argument to sort in 3.x because

• cmp functions are prone to produce inconsistent results in subtle ways, resulting in subtle and hard-to-find bugs
• cmp functions are slower
• it's almost always possible to convert a cmp function to a better performing key function

Programmer named 'System Down' has correctly described the situation, it's just that for Python 3, we can also use following code.

For Python 3:

import functools

def greater(a, b):
if (a % b) % 2 == 0:
return 1
return -1

x = [2,7,5,10,30,15]

print(sorted(x, key=functools.cmp_to_key(greater)))

protected by gnatApr 12 at 17:14

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?