Using a comparator function to sort

Question

So I'm working with a few pre-existing comparators that compare certain values in two tuples and return true if the first is greater than the second, false if otherwise. Here's the code for one of them:

def cmpValue(subInfo1, subInfo2):
    """
    Returns True if value in (value, work) tuple subInfo1 is GREATER than
    value in (value, work) tuple in subInfo2
    """
    # TODO...
    if subInfo1[0] > subInfo2[0]:
        return True
    else:
        return False

Now, I have a dictionary that has numerous tuple entries of the type being compared above. I want to sort them all in reverse order, but I don't really understand how I would accomplish that. I was thinking something like:

sortedDict = sorted(subjects, key=comparator, reverse = True)

But I don't know what to pass into the comparator because each comparator takes two arguments (subInfo1, subInfo2). I cannot change the comparator functions.

Varicocele

Comparator functions are deprecated in Python; use key functions instead. – Cornell

if condition: return True else: return False should be return condition. – Oarfish

Dictionaries do not preserve order. If you want a sorted dictionary you should use OrderedDict from the collections module. – Verdun

@IgnacioVazquez-Abrams : I miss a link to the deprecation declaration of the cmp operator. Here it is... The python wiki has an article how to convert from cmp to key. – Stalinist

Answer 1

You're passing the comparator as the key function. You should be passing it as the cmp, wrapped in some kind of function that turns it into a proper comparator.

def make_comparator(less_than):
    def compare(x, y):
        if less_than(x, y):
            return -1
        elif less_than(y, x):
            return 1
        else:
            return 0
    return compare

sortedDict = sorted(subjects, cmp=make_comparator(cmpValue), reverse=True)

(Although actually, you should be using key functions:

sorted(subjects, operator.itemgetter(0), reverse=True)

Also note that sortedDict will not actually be a dict, so the name is rather confusing.)

Oarfish

Also, the comparator should not return True or False but rather -1, 0, or 1. – Calica

Nice work on the wrapper function for the comparator. You might mention functools.cmp_to_key also. – Calica

functools.cmp_to_key is available for this sort of thing – Decato

Note that this is deprecated. See @IgnacioVazquez-Abrams or my answer in the comments of the question. – Stalinist

Answer 2

In Python 3 there is no cmp argument for the sorted function (nor for list.sort).

According to the docs, the signature is now sorted(iterable, *, key=None, reverse=False), so you have to use a key function to do a custom sort. The docs suggest:

Use functools.cmp_to_key() to convert an old-style cmp function to a key function.

Here's an example:

>>> def compare(x, y):
...     return x[0] - y[0]
... 
>>> data = [(4, None), (3, None), (2, None), (1, None)]
>>> from functools import cmp_to_key
>>> sorted(data, key=cmp_to_key(compare))
[(1, None), (2, None), (3, None), (4, None)]

However, your function doesn't conform to the old cmp function protocol either, since it returns True or False. For your specific situation you can do:

>>> your_key = cmp_to_key(make_comparator(cmpValue))
>>> sorted(data, key=your_key)
[(1, None), (2, None), (3, None), (4, None)]

using the make_comparator function from @Fred Foo's answer.

Zendah

Answer 3

The answer of @kaya3 is correct. I just propose another implementation in which we can use boolean for the comparator.

class YourTupleComparator(tuple):
    def __lt__(self, other):
        return self[0] < other[0]

sorted(subjects, key=YourTupleComparator)

Sturgill

Could you provide an explanation why could we do that? – Retentive

@Retentive what do you want to know? – Sturgill

Your answer looks elegant. However, I have no clue why it works (such as why only __lt__ is enough?). It does not on Python's official guide either. – Retentive

@Retentive it is kind of implied here: docs.python.org/3/reference/datamodel.html#object.__lt__ the default implementations return NotImplemented, upon finding that the sorting method flips the arguments using the symmetric operator... so you can implement only __gt__ and it would also work (after trying key(a) < key(b) it would attempt with key(b) > key(a)). But this depends on the sorting algorithm implementation, a more robust option would be using functools.total_ordering – Kimbrakimbrell

Answer 4

I don't know how does the answer of @Tuan Chau work. However, it may fail in complex situations.

Consider this comparison: each element is a tuple with two dimension. Element A is less than B if one of two conditions met: 1. A[0] is less than B[0]. 2. A[0]==B[0] and A[1]>B[0]. Therefore (1, 2) < (2, 1), (1, 2) < (1, 1).

Try the following snippets:

from functools import cmp_to_key

class Character(tuple):
    def __le__(self, other) -> bool:
        if self[0] < other[0] or (self[0] == other[0] and self[1] >= other[1]):
            return True
        return False


def compare(x, y):
    if x[0] == y[0]:
        return y[1] - x[1]
    return x[0] - y[0]


if __name__ == "__main__":
    array = [[1, 1], [2, 1], [2, 2], [1, 2]]
    print(sorted(array, key=Character))  # [[1, 1], [1, 2], [2, 1], [2, 2]]

    print(sorted(array, key=cmp_to_key(compare)))  # [[1, 2], [1, 1], [2, 2], [2, 1]]

As you can see, the result of class Character is wrong.

Retentive

Answer 5

We can now use this to sort a 2-D array:

A.sort(key=lambda a: (a[0], -a[1]))

This will sort the 2d-array by ascending order of A[0] and descending order of A[1].

Cilicia

This answer does not seem to be related to the question, which is about using comparator functions to sort. A key function is not a comparator function. It looks like you are trying to answer a different question like this one, though that question already has an answer saying the same thing so there is no need to write it again. – Zendah

This answer is related to this! Now instead of comparator we can use key in Python3 which works as a comparator. – Cilicia

it is related yes, but does not directly answer the question: it is only a unary function of one parameter and not a binary function of both parameters. – Warmhearted