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!

Introduction

Today we will discuss some tips on manipulating lists in Python 3 that will help you especially in competitive programming

We will discuss four techniques:

• Performing Multiple Swaps on Rows and columns Efficiently

• Initializing a 2D Matrix

• Deleting an Element from a List That You’re Iterating Upon

• Getting the Transpose of a Matrix

Performing Multiple Swaps on Rows and columns Efficiently

Steps:

• Store the matrix in a list of lists

• Create two dictionaries, one for the rows (that has size equal to the number of rows), and another for the columns (has size equal to the number of columns)

• Both keys and values are initialized to the initial indexing of the matrix

• The keys for those dictionaries are the original value for the indices of the matrix, the values are the indices after all swap operations

• We will access matrix elements using those dictionaries only

Sample Code:

matrix = [[1, 2, 3], [4, 5, 6]]

col = {i : i for i in range (3)} # creating columns map
row = {i : i for i in range (2)} # creating rows map

# I will perform three swaps, but you could extend to way more than that!
col[0], col[1] = col[1], col[0] # first swap
row[0], row[1] = row[1], row[0] # second swap
col[2], col[0] = col[0], col[2] # third swap

for i in matrix : # printing the original matrix before the swaps
    print (i)
'''
output:
[1, 2, 3]
[4, 5, 6]
'''

# printing the matrix after the swaps
for i in range (2) : # iterate through the whole matrix
    for j in range (3) :
        print (matrix [row[i]][col[j]], end = ' ') # accessing the matrix using the two maps
    print ()
'''
output:
6 4 5 
3 1 2 
'''

Initializing a 2D Matrix

It seems like an easy topic, but there is a trick that a lot of people don’t get at the first glance

I will show you the wrong way that many got mistaken over, then I will show you the correct method of doing it

The Wrong Method

• This method will create four references, all to the same 1-D list
• If you changed any element in the first 1-D list, it will affect the rest of the lists (will affect all elements with the same index as in the first list)

• This is because the reference of the first list is the same reference to the rest of the list

Sample Code:

# The WRONG way
# DO NOT DO THIS!
matrix = [[0] * 3] * 4 # initialization
matrix[0][0] = 1 # change
for i in matrix :
    print (i)
'''
output:

[1, 0, 0]
[1, 0, 0]
[1, 0, 0]
[1, 0, 0]
[1, 0, 0]
'''

The Right Method

• We will use a for loop, It's equivalent to writing multiple statements
• This will create multiple references, one for each row (1-D list)

Sample Code:

matrix = [[0] * 3 for _ in range (4)] # initialization
matrix[0][0] = 1 # change
for i in matrix :
    print (i)
'''
output:

[1, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
'''

Deleting an Element from a List That You’re Iterating Upon

• If we deleted some elements from a list while iterating over it, we will get the following error:

IndexError: list index out of range

Steps of deleting elements from a list while iterating over it correctly:

• Let's call the array that we want to delete elements from (**arr**)

• Make a new boolean array, and we called it (**isDeleted**)

• If the current element should be deleted, then make the corresponding element in the boolean array = 1

Note that: In the boolean array, the value of one means that the elements should be deleted, value of zero means otherwise

• Make a third array, we called it (**LAfterDeletion**), that will take the elements from arr that correspond to elements in the boolean array with a value of 0

Sample Code:

L = [1, 2, 3, 5, 66, 7, 8, 4, 23, 12] # making a list

isDeleted = [0] * len (L) # creating the boolean array
LAfterDeletion = [] # create the final array, that will take values after deletion

# Delete the elements that are larger than 5!
for i in range (len (L)) :
    if L[i] > 5 :
        isDeleted[i] = 1
for i in range (len (isDeleted)) :
    if isDeleted[i] == 0:
        LAfterDeletion.append(L[i])
print (LAfterDeletion) # [1, 2, 3, 5, 4]

Getting the Transpose of a Matrix

• The main idea is based on using the zip function

• Zip () function takes multiple iterables and returns a generator that contains a series of tuples, where each tuple contains a series of elements, one from each iterable

• We could cast this generator to a list

Sample Code:

lis = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # declaring the original list
for i in lis :
    print (i)
'''
output:

[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
'''
lis = list (zip (*lis)) # first rotation (replacing rows with columns)
# *lis is used to unpack the list of lists to multiple lists, equivalent to: lis[0], lis[1], lis[2]
for i in lis :
    print (i)
'''
output:
(1, 4, 7)
(2, 5, 8)
(3, 6, 9)
'''

That's it! I hope you learned from it. Happy coding!

I published it also in ..