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.

Introduction

Sorting is a fundamental concept in computer science and programming. It involves arranging data in a specific order, typically ascending or descending. Sorting is crucial because it enhances the efficiency of other algorithms that require sorted data, such as search algorithms. Common scenarios where sorting is useful include organizing a list of names alphabetically, arranging numbers in numerical order, and sorting data based on specific attributes.

Understanding the Basics

Before diving into complex sorting techniques, it's essential to understand the basic concepts. Sorting can be done in various ways, and Python provides a built-in sort() method to simplify this task. The sort() method can sort data in ascending or descending order and even allows custom sorting using a key function.

For example, consider a list of numbers:

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

By default, the sort() method sorts the list in ascending order. Understanding this basic functionality is crucial before moving on to more advanced sorting techniques.

Main Concepts

The sort() method in Python is versatile and can be customized using the key and reverse parameters. The key parameter allows you to define a function that determines the sorting order, while the reverse parameter sorts the list in descending order if set to True.

For instance, to sort a list of strings by their length, you can use the key parameter with the len() function:

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

This example demonstrates how the key parameter can be used to customize the sorting order based on specific criteria.

Examples and Use Cases

Let's explore some examples to understand the practical applications of sorting in Python.

1. Sorting a list of names in descending order:

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

2. Sorting an array of pairs based on custom criteria:

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]]

In this example, the pairs are sorted first by the sum of their elements in ascending order and then by the second element in descending order if the sums are equal.

Common Pitfalls and Best Practices

When using the sort() method, it's essential to avoid common mistakes such as:

Not understanding the default behavior of the sort() method, which sorts in ascending order.
Misusing the key parameter by not providing a valid function.
Forgetting that the sort() method sorts the list in place, modifying the original list.

Best practices for sorting include:

Using the key parameter to customize sorting based on specific criteria.
Using the sorted() function if you need to maintain the original list and get a sorted copy instead.
Writing clear and concise key functions, possibly using lambda functions for simplicity.

Advanced Techniques

Advanced sorting techniques involve more complex criteria and custom key functions. For example, you can sort a list of dictionaries based on multiple keys:

data = [{'name': 'Alice', 'age': 25}, {'name': 'Bob', 'age': 20}, {'name': 'Charlie', 'age': 25}]
data.sort(key=lambda x: (x['age'], x['name'])) # --> [{'name': 'Bob', 'age': 20}, {'name': 'Alice', 'age': 25}, {'name': 'Charlie', 'age': 25}]

This example sorts the list of dictionaries first by age and then by name if the ages are equal.

Code Implementation

Let's implement a comprehensive example that demonstrates various sorting techniques:

# List of numbers
numbers = [11, 3, 7, 5, 2]
numbers.sort() # Sort in ascending order
print(numbers) # Output: [2, 3, 5, 7, 11]

# List of names
names = ["Mircea", "Andy", "Xavier", "Michael", "Christina"]
names.sort(reverse=True) # Sort in descending order
print(names) # Output: ['Xavier', 'Mircea', 'Michael', 'Christina', 'Andy']

# List of words sorted by length
words = ['banana', 'pie', 'Washington', 'book']
words.sort(key=len) # Sort by length
print(words) # Output: ['pie', 'book', 'banana', 'Washington']

# List of pairs sorted by custom criteria
pairs = [[2, 3], [1, 7], [4, 4], [1, 4]]
pairs.sort(key=lambda a: [a[0] + a[1], -a[1]]) # Custom sort
print(pairs) # Output: [[1, 4], [2, 3], [1, 7], [4, 4]]

Debugging and Testing

When debugging sorting code, ensure that the key function returns the expected values for each element. Use print statements to verify the intermediate results. For testing, write test cases that cover various scenarios, including edge cases.

Example test case:

def test_sorting():
    numbers = [11, 3, 7, 5, 2]
    numbers.sort()
    assert numbers == [2, 3, 5, 7, 11]

    names = ["Mircea", "Andy", "Xavier", "Michael", "Christina"]
    names.sort(reverse=True)
    assert names == ['Xavier', 'Mircea', 'Michael', 'Christina', 'Andy']

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

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

test_sorting()

Thinking and Problem-Solving Tips

When approaching sorting problems, consider the following strategies:

Understand the default behavior of the sorting method.
Identify the criteria for sorting and whether custom sorting is needed.
Break down complex sorting criteria into simpler key functions.
Practice with various examples to gain confidence in using the sort() method.

Conclusion

Sorting is a fundamental concept in programming that enhances the efficiency of various algorithms. Understanding the basics of the sort() method in Python, along with its advanced features, is crucial for writing efficient and maintainable code. Practice sorting with different data types and criteria to master this essential skill.

Additional Resources

For further reading and practice, consider the following resources: