sorted ​

Sorting is a commonly used algorithm in programming. Whether using bubble sort or quick sort, the core of sorting is comparing the size of two elements. If they are numbers, we can compare them directly, but what if they are strings or dictionaries? Comparing their mathematical size doesn't make sense, so the comparison process needs to be abstracted into a function.

Python's built-in sorted() function can sort lists:

>>> sorted([36, 5, -12, 9, -21])
[-21, -12, 5, 9, 36]

The sorted() function is also a higher-order function, which can accept a key function to implement custom sorting. For example, sorting by absolute values:

>>> sorted([36, 5, -12, 9, -21], key=abs)
[5, 9, -12, -21, 36]

The key function applies to each element in the list and sorts based on the results returned by the key function. Comparing the original list and the list processed with key=abs:

list = [36, 5, -12, 9, -21]

keys = [36, 5,  12, 9,  21]

Then the sorted() function sorts based on the keys, and returns the corresponding elements of the list:

keys sort   => [5, 9,  12,  21, 36]
                |  |    |    |   |
result sort => [5, 9, -12, -21, 36]

Let's look at an example of string sorting:

>>> sorted(['bob', 'about', 'Zoo', 'Credit'])
['Credit', 'Zoo', 'about', 'bob']

By default, sorting strings is done according to ASCII values, and since 'Z' < 'a', uppercase letters appear before lowercase letters.

Now, if we want to sort while ignoring case sensitivity, we can achieve this by using a key function to map the strings for case-insensitive comparison. Ignoring case sensitivity involves converting all strings to uppercase (or lowercase) before comparison.

We can achieve case-insensitive sorting by passing a key function to sorted:

>>> sorted(['bob', 'about', 'Zoo', 'Credit'], key=str.lower)
['about', 'bob', 'Credit', 'Zoo']

To sort in reverse order, we can pass a third parameter reverse=True without changing the key function:

>>> sorted(['bob', 'about', 'Zoo', 'Credit'], key=str.lower, reverse=True)
['Zoo', 'Credit', 'bob', 'about']

From these examples, we can see that the abstraction capability of higher-order functions is very powerful, and the core code can remain extremely concise.

Summary ​

The sorted() function is also a higher-order function. The key to sorting with sorted() is implementing a mapping function.

Exercise ​

Suppose we use a list of tuples to represent students' names and grades:

L = [('Bob', 75), ('Adam', 92), ('Bart', 66), ('Lisa', 88)]

Sort the list by name:

L = [('Bob', 75), ('Adam', 92), ('Bart', 66), ('Lisa', 88)]

def by_name(t):
    return t[0]

L2 = sorted(L, key=by_name)
print(L2)

Now, sort by score in descending order:

L = [('Bob', 75), ('Adam', 92), ('Bart', 66), ('Lisa', 88)]

def by_score(t):
    return -t[1]

L2 = sorted(L, key=by_score)
print(L2)