sorting using a custom definition of ">" and "< " in python

Question

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?

Answer 1

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))

Answer 2

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

Answer 3

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)))