Python: Sorting list containing tuples

Question

I am still learning Python and I have been trying to sort this problem for hours but somehow cannot get it working: Suppose we have a list of tuples containing names and grades:

[("Mark", [5,4,1,2,4,3]), ("John", [1,2,3,1,2,1]), ("Patrick", [1,3,5,1,2,4])]

And we want to get this output:

[("John", [1,2,3,1,2,1]), ("Patrick", [1,3,5,1,2,4]), ("Mark", [5,4,1,2,4,3])]

, where the original list is is sorted in ascending order of students' marks score (suppose we get marks score by discarding the highest mark and adding all remaining marks together). I.e. John has marks 1,2,3,1,2,1, so we discard mark 3 and add 1+2+1+2+1 together, which gives us 7.

This task wouldnt be problem at all, if I wasnt required to get that output with all their original marks. I wrote this function:

def sortedFinalRes(input):
finalRes = 0
sortedRes = []
b = []
for i in range(0, len(input)):
    total = 0
    a = sorted(input[i][1], key = lambda x: x)
    a.pop()
    sortedRes += input[i][0], a
    total = sum(sortedRes[i*2+1])
    b += (sortedRes[i*2], total)
    c = sorted(b, key = lambda x: str(x))
print(sortedRes)
print(b)

, where I basically at first sort marks of each student so that I can then discard the highest one by using pop() and then I sum all remaining ones, which gives me marks score. Then I sort it according to marks score, but the output is required to be sorted, but with original marks, not with the mark score. Any ideas appreciated! Cheers

jme · Accepted Answer · 2014-12-12 19:56:34Z

5

We can define a scoring function like this:

def score(x): sum(x) - max(x)

This computes your so-called "marks score" by summing the scores and throwing out the max score. We'll then use it as a key for sorting, making sure to give it the second element of the tuple:

In [4]: sorted(d, key=lambda x: score(x[1]))                                                                                                                 
Out[4]: 
[('John', [1, 2, 3, 1, 2, 1]),
 ('Patrick', [1, 3, 5, 1, 2, 4]),
 ('Mark', [5, 4, 1, 2, 4, 3])]

edited Dec 12, 2014 at 19:56

answered Dec 8, 2014 at 19:08

jme

20.8k6 gold badges44 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Joran Beasley Over a year ago

great answer and snuck it in just before me :P

tdelaney Over a year ago

Why the double lambdas? Lambdas should never be assigned to variables, it misses the point. How about sorted(d, key=lambda x: sum(x) - max(x)) instead?

user2555451 Over a year ago

@tdelaney - sorted(d, key=lambda x: sum(x[1]) - max(x[1])) to be exact. x will be the tuples in the list. But good idea overall.

tdelaney Over a year ago

@JoranBeasley - oops, I should have looked more closely!

Joran Beasley · Accepted Answer · 2014-12-08 19:08:50Z

3

def sort_key(item):
    name,scores = item
    return sum(scores)-max(scores)
print sorted(students,key=sort_key)

you could easily do it with a single lambda as shown below ... I just did this for added verbosity

answered Dec 8, 2014 at 19:08

Joran Beasley

114k13 gold badges167 silver badges187 bronze badges

Comments

Kasravnd · Accepted Answer · 2014-12-08 19:46:45Z

1

you can refuse from max value by sorted(x[1])[:-1] that first sort the list and slice from beginning to highest:

>>> sorted (l,key=lambda x : sum(sorted(x[1])[:-1]))
[('John', [1, 2, 3, 1, 2, 1]), ('Patrick', [1, 3, 5, 1, 2, 4]), ('Mark', [5, 4, 1, 2, 4, 3])]

answers benchmark :

>>> s="""l=[("Mark", [5,4,1,2,4,3]), ("John", [1,2,3,1,2,1]), ("Patrick", [1,3,5,1,2,4])]
... sorted (l,key=lambda x : sum(sorted(x[1])[:-1]))"""
>>> timeit.timeit(stmt=s, number=100000)
0.407818078994751

>>> s="""l=[("Mark", [5,4,1,2,4,3]), ("John", [1,2,3,1,2,1]), ("Patrick", [1,3,5,1,2,4])]
... sorted(l, key=lambda x: sum(x[1]) - max(x[1]))"""
>>> timeit.timeit(stmt=s, number=100000)
0.3033828830718994

>>> s="""l=[("Mark", [5,4,1,2,4,3]), ("John", [1,2,3,1,2,1]), ("Patrick", [1,3,5,1,2,4])]
... def sort_key(item):
...     name,scores = item
...     return sum(scores)-max(scores)
... sorted(l,key=sort_key)"""
>>> timeit.timeit(stmt=s, number=100000)
0.2999439334869385

As you can see there no much difference between all the answers , any way Joran Beasley's answer is the best !

edited Dec 8, 2014 at 19:46

answered Dec 8, 2014 at 19:10

Kasravnd

108k19 gold badges167 silver badges195 bronze badges

13 Comments

iruvar Over a year ago

This is actually nlogn whereas the other solution is n

Kasravnd Over a year ago

@1_CR how you think that using max inside sorted has n order ?

jme Over a year ago

Actually, if n is the size of the outer list, and m is the size of the inner, this solution is O(n m log m + n log n), whereas solution with max is O(nm + n log n), I believe.

Kasravnd Over a year ago

@PadraicCunningham actually i mean as its key ! but any way im sure that order is not n

jme Over a year ago

@PadraicCunningham The key function sum(x) - max(x) takes time O(m), where m is the size of the score list. We have to evaluate the key function for each of the n entries, giving O(mn). Then we need to sort n keys, adding the O(n log n).

|

Collectives™ on Stack Overflow

Python: Sorting list containing tuples

3 Answers 3

4 Comments

Comments

13 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

13 Comments

Your Answer

Sign up or log in

Post as a guest

Related