Sorting in Python 3 for Competitive Programming

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!