Sorting in Python

The sort() method sorts the elements of a given array in ascending order, descending order or user-defined order.

Syntax:

The syntax of the sort() method is:

list.sort(key=..., reverse=...)

By default, sort() doesn't require any extra parameters. However, it has two optional parameters:

• reverse - If True, the sorted list is reversed (or sorted in Descending order)
• key - function that serves as a key for the sort comparison

Without extra arguments given, sort() will sort the array in ascending order by default:

numbers = [11, 3, 7, 5, 2]

numbers.sort() # --> [2, 3, 5, 7, 11]

With reverse=True, it will sort the array in descending order:

names = ["Mircea", "Andy", "Xavier", "Michael", "Christina"]

names.sort(reverse=True) # --> ['Xavier', 'Mircea', 'Michael', 'Christina', 'Andy']

Sort with custom function using key:

One of the most powerful components of sort() is the keyword argument called key. This argument expects a function to be passed to it, and that function will be used on each value in the list being sorted to determine the resulting order.

To demonstrate a basic example, let’s assume the requirement for ordering a specific list is the length of the strings in the list, shortest to longest. The function to return the length of a string, len(), will be used with the key argument:

words = ['banana', 'pie', 'Washington', 'book']

words.sort(key=len) # --> ['pie', 'book', 'banana', 'Washington']

The resulting order is a list with a string order of shortest to longest. The length of each element in the list is determined by len() and then returned in ascending order.

Note that key does not manipulate the data in the original list. During sorting, the function passed to key is being called on each element to determine sort order, but the original values will be in the output.

Example: sorting array of pairs

Let's say we want to sort an array, where each element is another array consisting of two numbers.

Python knows how to sort an array of arrays and that is: increasing by the 1st value, then increasing by the 2nd value, etc. For example:

pairs = [[1, 5], [12, 5], [10, 1], [1, 3]]

pairs.sort() # --> [[1, 3], [1, 5], [10, 1], [12, 5]]

However, let's say we want a different order - ascending by the sum and in case of equality, descending by the second values:

pairs = [[2, 3], [1, 7], [4, 4], [1, 4]]

# sort the array

# Desired outcome: pairs = [[1, 4], [2, 3], [1, 7], [4, 4]]

Solution:

pairs = [[2, 3], [1, 7], [4, 4], [1, 4]]

# key function
def key_func(a):
  return [a[0] + a[1], -a[1]]

pairs.sort(key=key_func) # --> pairs = [[1, 4], [2, 3], [1, 7], [4, 4]]

As you can see, key_func() takes an array as argument and returns another one consisting of:

• a[0] + a[1] - in order to sort the arrays first by the sum in ascending order
• -a[1] - in case of equal sum arrays, it will sort by -a[1] in ascending order e.g. by a[1] in descending order

We can write the code above in a shorter manner using lambda functions:

pairs = [[2, 3], [1, 7], [4, 4], [1, 4]]

pairs.sort(key=lambda a: [a[0] + a[1], -a[1]]) # --> pairs = [[1, 4], [2, 3], [1, 7], [4, 4]]

Time Complexity:

Sorting an array via sort() takes O(n * log n * C) time, where C is the time taken to compare two elements from the array.

It takes O(1) (constant time) to compare two numbers, therefore sorting an array of numbers takes O(n log n).

However, it takes O(L) to compare two strings, therefore sorting an array of strings takes O(n * log n * L), where L is the average length of the strings.

Space Complexity:

The sort() method sorts the elements of an array in place (transforms the array directly, using no auxiliary data structure), so the extra space used for this is O(1).

Assignment
Follow the Coding Tutorial and let's sort some arrays.

Hint
Look at the examples above if you get stuck.