194

I know there are several questions named like this, but they don't seem to work for me.

I have a list of lists, 50 times 5 elements. I want to sort this list by applying a custom compare function to each element. This function calculates the fitness of the list by which the elements shall be sorted. I created two functions, compare and fitness:

def compare(item1, item2):
    return (fitness(item1) < fitness(item2))

and

def fitness(item):
    return item[0]+item[1]+item[2]+item[3]+item[4]

Then I tried to call them by:

sorted(mylist, cmp=compare)

or

sorted(mylist, key=fitness)

or

sorted(mylist, cmp=compare, key=fitness)

or

sorted(mylist, cmp=lambda x,y: compare(x,y))

Also I tried list.sort() with the same parameters. But in any case the functions don't get a list as an argument but a None. I have no idea why that is, coming from mostly C++ this contradicts any idea of a callback function for me. How can I sort this lists with a custom function?

Edit I found my mistake. In the chain that creates the original list one function didn't return anything but the return value was used. Sorry for the bother

Improve this question
3
  • 4
    Show code, what you expect and what you get. Commented Mar 6, 2011 at 20:15
  • 4
    Note that your compare function is incorrect, since it only returns True or False, and doesn't distinguish between item1 and item2 being equal and item1 being greater than item2. The correct way to write compare would be to return cmp(fitness(item1), fitness(item2)). But using key is better. Commented Mar 7, 2011 at 10:04
  • 4
    cmp keyword was removed in Python 3. You can now use key=functools.cmp_to_key(<function>) after importing functools. Commented Feb 3, 2020 at 22:02

7 Answers 7

Reset to default
197

Since the OP was asking for using a custom compare function (and this is what led me to this question as well), I want to give a solid answer here:

Generally, you want to use the built-in sorted() function which takes a custom comparator as its parameter. We need to pay attention to the fact that in Python 3 the parameter name and semantics have changed.

How the custom comparator works

When providing a custom comparator, it should generally return an integer/float value that follows the following pattern (as with most other programming languages and frameworks):

  • return a negative value (< 0) when the left item should be sorted before the right item
  • return a positive value (> 0) when the left item should be sorted after the right item
  • return 0 when both the left and the right item have the same weight and should be ordered "equally" without precedence

In the particular case of the OP's question, the following custom compare function can be used:

def compare(item1, item2):
    return fitness(item1) - fitness(item2)

Using the minus operation is a nifty trick because it yields to positive values when the weight of left item1 is bigger than the weight of the right item2. Hence item1 will be sorted after item2.

If you want to reverse the sort order, simply reverse the subtraction: return fitness(item2) - fitness(item1)

Calling sorted() in Python 2

sorted(mylist, cmp=compare)

or:

sorted(mylist, cmp=lambda item1, item2: fitness(item1) - fitness(item2))

Calling sorted() in Python 3

from functools import cmp_to_key
sorted(mylist, key=cmp_to_key(compare))

or:

from functools import cmp_to_key
sorted(mylist, key=cmp_to_key(lambda item1, item2: fitness(item1) - fitness(item2)))
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Note that cmp_to_key serves to change the Python 2 style compare() function to what is needed for Python 3.
It not only serves for a replacement of the Python 2 style, cmp_to_key also allows to provide a comparator which compares two elements directly which is convenient for those cases where you can't or don't want to directly map a list element to a value.
This is the most complete, should accepted answer.
Bless you for figuring this out. Everything about the Py3 syntax is unintuitive to the uninitiated; the name of the function (past participle rather than verb), the parameter name (key evokes nothing useful to the reader), and the magical incantation cmp_to_key.
It's called "sorted" because it returns a sorted copy of the original list. The verb "sort" is a method on the list, and does an in-place sort. I agree that the change to "key" rather than "compare" is a bit unintuitive though.
Worth mentioning the source code for cmp_to_key. To me it was a little confusing how to convert my existing compare function (which easily handled partial ordering) to a key that could handle total ordering across all values. Especially since the values I was working with had no total order (a graph with cycles), but the subsets of it I looked at were orderable (no cycles). For anyone interested, it was this problem: adventofcode.com/2024/day/5
170

Also, your compare function is incorrect. It needs to return -1, 0, or 1, not a boolean as you have it. The correct compare function would be:

def compare(item1, item2):
    if fitness(item1) < fitness(item2):
        return -1
    elif fitness(item1) > fitness(item2):
        return 1
    else:
        return 0

# Calling
list.sort(key=compare)

Works with Python 2

Improve this answer

6 Comments

or just, return fitness(item1) - fitness(item2). The compare function does not have to return -1 or 1, but merely a negative or positive number (or zero). Ref: docs.python.org/2/library/stdtypes.html#mutable-sequence-types
sorted(myList, key=lambda x: -fitness(x))
or sorted(myList, key=fitness, reverse=True)
For py3, use key=functools.cmp_to_key(compare). See answer by JustAC0der
@marverix That's right. I wasn't excluding zero in my comment.
|
54

You need to slightly modify your compare function and use functools.cmp_to_key to pass it to sorted. Example code:

import functools

lst = [list(range(i, i+5)) for i in range(5, 1, -1)]

def fitness(item):
    return item[0]+item[1]+item[2]+item[3]+item[4]
def compare(item1, item2):
    return fitness(item1) - fitness(item2)

sorted(lst, key=functools.cmp_to_key(compare))

Output:

[[2, 3, 4, 5, 6], [3, 4, 5, 6, 7], [4, 5, 6, 7, 8], [5, 6, 7, 8, 9]]

Works :)

Improve this answer

Comments

30 
>>> l = [list(range(i, i+4)) for i in range(10,1,-1)]
>>> l
[[10, 11, 12, 13], [9, 10, 11, 12], [8, 9, 10, 11], [7, 8, 9, 10], [6, 7, 8, 9], [5, 6, 7, 8], [4, 5, 6, 7], [3, 4, 5, 6], [2, 3, 4, 5]]
>>> sorted(l, key=sum)
[[2, 3, 4, 5], [3, 4, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8], [6, 7, 8, 9], [7, 8, 9, 10], [8, 9, 10, 11], [9, 10, 11, 12], [10, 11, 12, 13]]

The above works. Are you doing something different?

Notice that your key function is just sum; there's no need to write it explicitly.

Improve this answer

2 Comments

You are absolutly right, some other code caused the error, thank you. And thanks you again, at least now I have an example that uses a function instead of a lambda expression as key value. I couldn't find one when I looked for a solution before.
Doesn't answer the question. The question asked for a custom comparator, none was shown.
9

For python3x

arr = [1, 33, 23, 56, 9]

def compare_func(x, y):
     return x - y

1.Use arr.sort with compare function

arr.sort(key=cmp_to_key(compare_func))

2.Use sorted for getting new list

new_list = sorted(arr, key=cmp_to_key(lambda x, y: x - y)))

3.Use arr.sort with lambda

arr.sort(key=cmp_to_key(lambda x, y: x - y))
Improve this answer

Comments

7

One simple way to see it is that the sorted() (or list.sort()) function in Python operates on a single key at a time. It builds a key list in a single pass through the list elements. Afterwards, it determines which key is greater or lesser and puts them in the correct order.

So the solution, as I found, was to make a key which gives the right order. Here, Python can use a key as a str or tuple. This does not require the functools module as in other examples:

# task: sort the list of strings, such that items listed as '_fw' come before '_bw'
foolist = ['Goo_fw', 'Goo_bw', 'Foo_fw', 'Foo_bw', 'Boo_fw', 'Boo_bw']

def sortfoo(s):
    s1, s2 = s.split('_')
    r = 1 if s2 == 'fw' else 2     # forces 'fw' to come before 'bw'
    return (r, s1)                 # order first by 'fw'/'bw', then by name

foolist.sort(key=sortfoo)          # sorts foolist inplace

print(foolist)
# prints:
# ['Boo_fw', 'Foo_fw', 'Goo_fw', 'Boo_bw', 'Foo_bw', 'Goo_bw']

This works because a tuple is a legal key to use for sorting. This can be customized as you need, where the different sorting elements are simply stacked into this tuple in the order of importance for the sort.

Improve this answer

Comments

5

I stumbled on this thread to sort the list of lists by comparator function. For anyone who is new to python or coming from a c++ background. we want to replicate to use of the call-back function here like c++. I tried this with the sorted() function.

For example: if we wanted to sort this list according to marks (ascending order) and if marks are equal then name (ascending order)

students= [['Harry', 37.21], ['Berry', 37.21], ['Tina', 37.2], ['Akriti', 41.0], ['Harsh', 39.0]]

def compare(e):
  return (e[1],e[0])

students = sorted(students,key=compare)

After Sorting:

[['Tina', 37.2], ['Berry', 37.21], ['Harry', 37.21], ['Harsh', 39.0], ['Akriti', 41.0]]
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.