Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 3 down vote accepted

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))
share|improve this answer
    
this is exactly what I was looking for! thanks I"m using python 2.7.2 – user5198 Jun 1 '12 at 0:40
3  
I still can't believe removal of cmp was deemed a good idea for 3.x... – Izkata Jun 1 '12 at 2:19
1  
@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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.