Custom compare function in python3

Question

I want to sort points in 2D coordinate system by their distance to the origin (0,0) in increasing order. I found this and tried something, but still I could not get desired result.

Here is my code:

from functools import cmp_to_key

def my_comp(point1, point2):
    return point1[0]*point1[0] + point1[1]*point1[1] < point2[0]*point2[0] + point2[1]*point2[1]

points = [ [3.1, 4.1], [0.9, 0.8], [1.0, 1.0] ]
sorted(points, key=cmp_to_key(my_comp))
print(points)

Result:

[[3.1, 4.1], [0.9, 0.8], [1.0, 1.0]]

Expected:

[[0.9, 0.8], [1.0, 1.0], [3.1, 4.1]]

Answer 1

1) Your my_cmp() function is supposed to return one of three values (+, -, or 0 depending upon the compare), but you only return two (True and False).

2) You ingnore the return value from sorted(). sorted() doesn't modify its argument, it returns a sorted copy of it.

3) Don't use cmp functions. They are hard to describe and hard to implement. Instead use key functions.

How about:

def my_key(point1):
    return point1[0]*point1[0] + point1[1]*point1[1]

points = [ [3.1, 4.1], [0.9, 0.8], [1.0, 1.0] ]
points = sorted(points, key=my_key)
print(points)

assert points == [ [0.9, 0.8], [1.0, 1.0], [3.1, 4.1] ]

Answer 2

Does this do what you want?

sorted_points = sorted(points, key=lambda p: p[0]*p[0] + p[1]*p[1])

Another thing to watch out for in your original code is that sorted does not sort the list in place, it creates a new list that is sorted. So when you do

points = [3,2,1]
sorted(points)
print(points)

It will appear that your code hasn't sorted anything because you are printing the original list not the newly created sorted one. You can perform a sort in place like so.

points = [3,2,1]
points.sort()
print(points)

Answer 3

It looks like you are going through some extra hoops here. You have a quantity that is already a perfect key. Instead of just using it, you define a comparator that recomputes and compares two of these quantities for every pair of objects, and then convert that comparator back to a key.

This seems very inefficient. Why not just define a simple key function and use it directly?

def distance_from_origin_squared(point):
    return point[0]**2 + point[1]**2
points = sorted(points, key=distance_from_origin_squared)

Keep in mind that sorted does not operate in-place, so you have to stash it somewhere. Replacing the original name if fine. If you want an in-place sort, use list.sort instead:

points.sort(key=distance_from_origin_squared)

From a practical point of view, keys offer a number of advantages over comparators. For one thing, a key function only needs to be called once per element, while a comparator is called O(nlog(n)) times. Of course the keys are compared O(nlog(n)) times, but the comparison is usually much simpler since the values of interest are computed up front.

The main difficulty coming from C (in my case) is grasping the idea that keys do not have to be single integers, as is usually shown in examples. Keys can be any type that clearly defines the < (or >) operator. Lexicographical comparison of strings, lists and tuples makes it very easy to boil a complex chained comparator to a key that is just a short sequence of values.

Answer 4

You're confusing the cmp and key arguments. A cmp function accepts two arguments and returns -1, 0, or 1. A key function returns a proxy value that will be used to sort the list. cmp was removed as an argument to sorted in Python 3.