Sort a list based on two different criteria using Sorted

Asked

Viewed 341 times

4

I have a list of tuples and I want to sort them out, but that’s two different criteria.

Each tuple has the following configuration: (peso, beneficio)

The ordination I want to make is as follows:

From the element with the highest benefit to the one with the lowest benefit. If two tuples have the same benefit value, the tiebreaker criterion is the weight. The tuple with the lowest weight gains.

Therefore, given the list of tuples:

[(4,2),(5,2),(7,3),(9,4),(6,4)]

The sorted list shall be:

[(6,4),(9,4),(7,3),(4,2),(5,2)]

To use two elements as sorting criteria I found this solution. But trying to use returns the two fields with the same criterion.

listaqq = [(4,2),(5,2),(7,3),(9,4),(6,4)]
sortedLista = sorted(listaqq, key=operator.itemgetter(1,0), reverse=True)

[(9, 4), (6, 4), (7, 3), (5, 2), (4, 2)]

Giving another sought here I found this possible solution, but I could not understand to apply the way I need.

There would be some way to do it using sorted?
Maybe using lambda, but how would the expression?

3 answers

3

The "key" parameter accepts any function, which will receive an element of the sequence that will be ordered, and must return an element that can be directly compared with ">" and "<" by Python.

The standard of using "itemgetter" is to take advantage of this already existing feature so that the code becomes more elegant - but I personally think it complicates readability. (itemgetter may also have a small performance gain - but it would have to be a very specific code snippet to really make a difference - for example, if it’s a sort in millions of results.)

In short, you just create your own key function. How Python can compare tuples, comparing the first item, and draw, comparing the second item. In your specific case, just flip the tuple - return a tuple in which the benefit is compared before the weight:

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

sortedLista = sorted(listaqq, key=comp, reverse=True)

Since functions of this type are generally simple, it is common to write the comparison function as a "lambda" function - it works exactly like a function, but can contain a single expression, and does not need the "Return" command":


sortedLista = sorted(listaqq, key=lambda item: (item[1], item[0]), reverse=True)
  • I don’t think that produces the expected result, because in the case will order by item[1] in descending order, and the tiebreaker with item[0] will also be in descending order (but the tie break should be in ascending order) - I left an answer with an alternative (but I don’t know if it was too much gambiarra or if it has a more elegant way - feel free to comment there)

  • ah - actually just do lambda item; -item[1], item[0] and take out the verse.

  • 1

    This - as Victor did there - I used sesse Pattern myself recently - I can’t even remember where.

3

To resolve this issue you can use the following code:

listaqq = [(4, 2), (5, 2), (7, 3), (9, 4), (6, 4)]
print(sorted(listaqq, key=lambda c: (-c[1], c[0])))

Note that in this code the lambda function is ordering listqq depending on the according to value of tupla and, in the case of empate, the tiebreaker will be given by first value of the respective tuple.

Now if you want to work with any tuple lists, with integer values, you can use the following code:

n = int(input('Quantos tuplas? '))
listaqq = list()
for d in range(1, n + 1):
    listaqq.append(tuple(map(int, input(f'Digite a {d}º tupla: ').split())))
print(sorted(listaqq, key=lambda c: (-c[1], c[0])))

When we execute this second code we must enter the amount of tuples we want to mount. Then we must enter all the values of each tuple, in the same line, separated for a single space and press enter.

The code will then sort the tuples according to the last index of each tuple.

  • 1

    Missed the tiebreaker when c[1] is the same, its code results in [(9, 4), (6, 4), (7, 3), (4, 2), (5, 2)] but the result should be [(6, 4), (9, 4), (7, 3), (4, 2), (5, 2)] - let an answer with an alternative to the tiebreaker

3


The problem of using itemgetter or tuples (as suggested in another answer) is that both elements will be ordered by the same criterion (either both in ascending order, or both in nonexistent order). Even if you use reverse=True, this will be applied in both.

If the idea is that one is in descending order and the other in ascending order, an alternative is to reverse the signal of one of them:

def comp(item): # primeiro item em ordem decrescente, segundo em ordem crescente
   return -item[1], item[0]

listaqq = [(4,2),(5,2),(7,3),(9,4),(6,4)]

sortedLista = sorted(listaqq, key=comp)
print(sortedLista) # [(6, 4), (9, 4), (7, 3), (4, 2), (5, 2)]

Or, using lambda instead of a function:

sortedLista = sorted(listaqq, key=lambda item: (-item[1], item[0]))

In that case you don’t need to use reverse=True. As I reversed the sign of the second element of the tuple, they will be ordered in descending order. In the case of a tie, the value of the first element will be used (in ascending order).

The result will be the list [(6,4),(9,4),(7,3),(4,2),(5,2)].


Already using the another solution that you saw:

def compare(t1, t2):
    # compara o segundo elemento de cada tupla, em ordem decrescente
    cmp = t2[1] - t1[1]
    if cmp == 0: # se forem iguais, compara o primeiro elemento de cada tupla, em ordem crescente
        cmp = t1[0] - t2[0]
    return cmp

import functools

sortedLista = sorted(listaqq, key = functools.cmp_to_key(compare))
print(sortedLista)

The idea is that the comparison function returns a negative number if the first element is "smaller" (i.e., whether it should come earlier in ordering), 0 if they are equal and a positive number if it is "higher" (if it should come later in ordering).

Then I can simply subtract the second element of the second tuple by the second element of the first: if the result is positive, that is to say that the first tuple must come later in the ordering (that is, the elements are ordered in descending order).

If the result of the subtraction is zero, that means that the second element of tuples are equal, and then I do the tiebreaker for the first element (but now subtracting the element from the first tuple before, so that it is in ascending order).

At last, I use cmp_to_key so that the comparison function is converted to a key Function and can be used in sorted.

Browser other questions tagged

You are not signed in. Login or sign up in order to post.