Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

AbdelrahmanDeghedy's blog

By AbdelrahmanDeghedy, history, 8 months ago, In English

Introduction

Today, we will discuss many cases for sorting in Python 3. It’s a must-have skill in competitive programming.

Explaining the Sort Function, and its Different Arguments.

By default, the sorting function, sorts in ascending order.

The sort function can take two optional arguments:

A- The reverse attribute: It takes a boolean value. True if the sorting is descending, false if ascending.

L = [3, 5, 1, 8, 5, 9]
L = sorted (L, reverse = True)
print (L)   # [9, 8, 5, 5, 3, 1]

B- The key attribute: It takes a comparison function (I will call it: key function throughout this article) for custom sorting.

The key function is applied to each element of the list, to create a pseudo list of the new values returned from that function. Then, the sorting is done based on the values of this pseudo list.

Note: We assign a function to the key attribute, not the return of a function.

Example:

L = ['g', 'a', 'n', 'A', 'B', 'r', 'Y']
L = sorted (L, key = str.lower)
print (L) # ['a', 'A', 'B', 'g', 'n', 'r', 'Y']

# sorts the characters after converting them to lowercase (dynamically on the fly)

Writing Our Own Comparison Function.

We can also write our user-defined key function.

How to write a sorting key function?

The function takes one argument that represents an element of the iterable.

Note: That element could be a single variable, a tuple, or even a list (in a list of lists for example).

The function will compute a value of each element, that we will sort upon.

Example:

'sorts based on the value of the (modulus by 10) of each element'
def keyFunc (element) :
    return element % 10

L = [1, 3, 6, 7, 9, 11]
L = sorted (L, key = keyFunc)
for i in L :
    print (i, end = " ")
''' 1 11 3 6 7 9 '''

Sorting Based on the i-th Element in a List of Tuples.

Suppose that we have a list of tuples, and we want to sort it based on the second element of each tuple.

Based on what we learned in the last section, we will write our own key function to handle that.

The argument of the key function corresponds to a tuple, that represents a single element of the list.

We will return the second element from that tuple, to sort based on it.

Example:

listOfTuples = [(1, 'c', 1), (0, 'a', 9), (5, 'h', 5)]
listOfTuples = sorted (listOfTuples, key = lambda iter : iter[1])
for i in listOfTuples :
    print (i)
'''
(0, 'a', 9)
(1, 'c', 1)
(5, 'h', 5)
'''

Secondary Sorting.

Consider the following scenario:

If we have a dictionary, and the keys are strings, values are integers, and we want to sort it based on the integers, but if two integers were equal, then sort based on their corresponding string values.

To do so, the key function will return an extra value, to define our second criteria.

Example:

def keyFunc (element) :
    return element[1], element[0]   # sorting based on values, then the keys

d = {'f' : 9, 'd' : 8, 'b': 8}
d = sorted (d.items (), key = keyFunc)
print (d)   # [('b', 8), ('d', 8), ('f', 9)]

More Complex Examples

What if we want to sort a dictionary based on ascending values, then by descending keys.

If the reverse attribute took the value of True, it will perform both the first and the second sorting in descending order.

If we added a negative sign in front of one of the return values of the key function, then it will have the opposite sorting effect that was set for it.

Example:

d = {'b': 9, 'd' : 8, 'f' : 8}
d = sorted (d.items (), key = lambda x : (-x[1], x[0]), reverse = True)    # sorting based on ascending values, then by descending keys
print (d)   # [('f', 8), ('d', 8), ('b', 9)]

Note: the negative sign can be added before an integer element only.

Example:

d = {'f' : 8, 'd' : 8, 'b': 9}
# we want to sort based on ascending values, then by descending keys
d = sorted (d.items (), key = lambda x : (x[1], -x[0])) # TypeError: bad operand type for unary -: 'str'

That's it for today! I hope you learned from it. Good Luck!

 
 
 
 
  • Vote: I like it
  • +14
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do something like this : We have a list of objects say Points : Points = [P1, P2, .... Pn].

And each point has two variables : x and y.

And I want to sort based on this function :

def cmp(a : Point, b : Point) -> bool:
        return a.x < b.x or (a.x == b.x and (a.y < b.y))
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If your compare function returns -1 for less than, 0 for equal, and 1 for greater than, you could use functools.cmp_to_key.

    However, it looks like the compare function you wrote as an example is sorting by "x" first and if the "x" values are equal, then sort by "y". In that case, you can do something like myPoints.sort(key=lambda point: (point.x, point.y))

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can some please explain how to sort by second element of second tuple in the list [(0, (2, 40)), (1, (3, 50)), (2, (4, 60)), (3, (5, 10)), (4, (6, 20))] this is how i created my list for i in range(len(A)): tuple1 = (A[i],B[i]) tuple2 = (i,tuple1) ans.append(tuple2)

ans.sort(key = sort_tuple(a:????)

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

general feedback: add context vs. other languages (c++ sure is popular here), therefore...

Emphasize the difference/transition between sort key and comparator. Using them interchangeably is glossing over that and leading to the questions seen so far in comments.

Optionally: algorithm characteristics, what's it good at? why is it especially necessary for python's sort to be good at that? -- I say optional only because it feels easier to explain than 'avoid quicksort because x, also it's the default for situations y, z, and gamma' seen for other languages... maybe not actually optional/easier. Maybe a note on order/stability in light of the key/comparator difference...

CODEFORCES-SPECIFIC PITFALL: while pypy3 is still 32-bit, you kinda just have to know things like sorting inputs with large integers is going to make it puke (TLE) as seen most recently in slay the dragon (1e12 why?). Workarounds are (cough) varied, but start with (re)submitting in python3. It's also assumed the contestant has already picked sufficient (-ly magical) io-go-fast measures.

edit: ahcrap, posting on a necropost...