How to use a custom comparator functions in python to sort a 2D list?

Question

I am trying to solve a problem: https://hack.codingblocks.com/app/practice/1/176/problem

The problem is to sort a list of lists on the basis of the 2nd element. For any two lists if the second element is the same then sort on the basis of the first element. The input is like this:

79
4
Eve 78
Bob 99
Suzy 86
Alice 86

And the output should be:

Bob 99
Alice 86
Suzy 86

This is the Python code that I have written.

 def compare(item1, item2):
    if item1[1] == item2[1]:
         return item1[0] < item2[0]
    else:
         return item1[1] < item2[1]

 ts = int(input())
 n = int(input())
 m = []
 for i in range(n):
      l = list(input().split())
      l[1] = int(l[1])
      m.append(l)
 sorted(m, key=compare, reverse=True) # or m.sort(key=compare, reverse=True)

 for i in range(n):
      if m[i][1] >= ts:
          print(m[i][0], m[i][1])

For both approaches sort/sorted, there is an error:

1. For sorted:

   TypeError: compare() missing 1 required positional argument: 'item2'

2. For sort:

   TypeError: compare() missing 1 required positional argument: 'item2'

The error is the same for both approaches.

Answer 1

You are confusing two concepts: a key function and a compare function. Although they can both be used as helpers for a sort, those are different types of functions.

Links to relevant documentation:

• Sorting with a key function;
• Sorting with a compare function.

A compare function inputs two items, and returns true or false to tell which one is smaller. A key function inputs one item, and returns a value that can easily be compared to the values of other items. Imagine if you're in a store and want to sort items by price: the key function you'll need is the one that returns the price of an item.

Here you want to sort according to the pair (item[1], item[0]). So you can do exactly that:

unsorted_list = [('Eve', 78), ('Bob', 99), ('Suzy', 86), ('Alice', 86) ]

def the_key(item):
  return (item[1], item[0])

sorted_list = sorted(unsorted_list, key=the_key)

If you're not planning on reusing function the_key later in your code, you might find this a bit tedious and want to avoid using the def keyword to define a named function. In that case, you can use lambda instead of def, to define an anonymous function:

unsorted_list = [('Eve', 78), ('Bob', 99), ('Suzy', 86), ('Alice', 86) ]

sorted_list = sorted(unsorted_list, key=lambda item: (item[1], item[0]))

Finally, since sorting according to some fields of a list is very common, rather than defined the key yourself with def or lambda, you can use the pre-existing functions from module operator:

from operator import itemgetter

unsorted_list = [('Eve', 78), ('Bob', 99), ('Suzy', 86), ('Alice', 86) ]

sorted_list = sorted(unsorted_list, key=itemgetter(1,0))

Further fitting your input example

In your input example, it appears some of your list only have one element, instead of two. Trying to refer to "the second element" of a list which has only one element is bound to crash the python interpreter. You could define a custom key function which handles one-element lists separately:

unsorted_list = [[79], [4], ['The answer is', 42, 'but this list is too long'], ['Eve', 78], ['Bob', 99], ['Suzy', 86], ['Alice', 86]]

def the_key(item):
  if len(item) >= 2:
    return (item[1], item[0])
  else:
    return (item[0], '')

sorted_list = sorted(unsorted_list, key=the_key)

# or with lambda
sorted_list = sorted(unsorted_list, key=lambda item: (item[1], item[0]) if len(item) >= 2 else (item[0], ''))

Note that this will still crash if some of the items are empty lists. If that might be the case, you should add a third case in the_key to handle empty lists, if you want these empty lists kept in the sorted list; or you can filter the list first, using a list comprehension or filter, to remove the empty items.