Every computer scientist loves sorting things. In this article, I’ll show you how Python does it—and how you can tap into the powerful sorting features of Python lists.
Definition and Usage: The list.sort() method sorts the list elements in place in an ascending manner. To customize the default sorting behavior, use the optional key argument by passing a function that returns a comparable value for each element in the list. With the optional Boolean reverse argument, you can switch from ascending (reverse=False) to descending order (reverse=True).
Here’s a short overview example that shows you how to use the arguments in practice:
# Create an unsorted integer list lst = [88, 12, 42, 11, 2] # Sort the list in place (ascending) lst.sort() print(lst) # [2, 11, 12, 42, 88] # Sort the list (leading number) lst.sort(key=lambda x: str(x)[0]) print(lst) # [11, 12, 2, 42, 88] # Sort the list in place (descending) lst.sort(reverse=True) print(lst) # [88, 42, 12, 11, 2]
In the first line of the example, you create the list lst. You then sort the list once using the default sorting behavior and once using a customized sorting behavior with only the first letter of the number. You then reverse the order of the elements in the sorted list using the reverse=True argument.
Code Puzzle — Try It Yourself:
Now you know the basics. Let’s deepen your understanding with a short code puzzle—can you solve it?
# Create an unsorted integer list lst = [88, 12, 42, 11, 2] # Sort the list in place (ascending) lst.sort() print(lst) # Sort the list (leading number) lst.sort(key=lambda x: str(x)[0]) print(lst) # Sort the list in place (descending) lst.sort(reverse=True) print(last) # What's the output of this code snippet?
You can also solve this puzzle and track your Python skills on our interactive Finxter app.
Syntax: You can call this method on each list object in Python (Python versions 2.x and 3.x). Here’s the syntax:
list.sort(key=None, reverse=False)
Arguments:
| Argument | Description |
|---|---|
key | (Optional. Default None.) Pass a function that takes a single argument and returns a comparable value. The function is then applied to each element in the list. Then, the method sorts based on the key function results rather than the elements themselves. |
reverse | (Optional. Default False.) The order of the list elements. If False, sorting is in ascending order. If True, it’s in descending order. |
Return value: The method list.sort() returns None, no matter the list on which it’s called. Why? Because it sorts a list in-place and doesn’t create a new list.
Related articles:
Python List Sort Key
The list.sort() method takes another function as an optional key argument that allows you to modify the default sorting behavior. The key function is then called on each list element and returns another value based on which the sorting is done. Hence, the key function takes one input argument (a list element) and returns one output value (a value that can be compared).
Here’s an example:
>>> lst = [(1,2), (3,2), (3,3), (1,0), (0,1), (4,2), (1,1), (0,2), (0,0)] >>> lst.sort() >>> lst [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (3, 2), (3, 3), (4, 2)] >>> lst.sort(key=lambda x: x[0]) >>> lst [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (3, 2), (3, 3), (4, 2)] >>> lst.sort(key=lambda x: x[1]) >>> lst [(0, 0), (1, 0), (0, 1), (1, 1), (0, 2), (1, 2), (3, 2), (4, 2), (3, 3)]
You can see that in the first two examples, the list is sorted according to the first tuple value first. In the third example, the list is sorted according to the second tuple value first. You achieve this by defining a key function key=lambda x: x[1] that takes one list element x (a tuple) as an argument and transforms it into a comparable value x[1] (the second tuple value).
Related article:
Python List Sort Itemgetter
You can use any function as a key function that transforms one element into another (comparable) element.
For example, it’s common to use the itemgetter() function from the operator module to access the i-th value of an iterable:
>>> from operator import itemgetter
>>> customers = [('alice', 1000), ('bob', 100), ('frank', 10)]
>>> customers.sort(key=itemgetter(1))
[('frank', 10), ('bob', 100), ('alice', 1000)]The itemgetter() function does exactly the same as the lambda function in the previous example: it returns the second tuple value and uses it as a basis for comparison.
Python List Sort with Two Keys
How to sort a list with two keys? For example, you have a list of tuples [(1,2), (3,2), (3,3), (1,0), (0,1), (4,2), (1,1), (0,2), (0,0)] and you want to sort after the second tuple value first. But if there’s a tie (e.g. (1,2) and (3,2)), you want to sort after the first tuple value. How can you do that?
Per default, Python sorts tuples lexicographically—the first tuple value is considered first. Only if there’s a tie, it takes the second tuple value and so on.
So to sort with “two keys”, you can define a key function that returns a tuple rather than only a single tuple value. Here’s an example:
>>> lst = [(1,2), (3,2), (3,3), (1,0), (0,1), (4,2), (1,1), (0,2), (0,0)] >>> lst.sort(key=lambda x: (x[1], x[0])) >>> lst [(0, 0), (1, 0), (0, 1), (1, 1), (0, 2), (1, 2), (3, 2), (4, 2), (3, 3)]
The second tuple value takes precedence over the first tuple value.
Python List Sort with Multiple Keys
How to sort a list with multiple keys? For example, you have a list of tuples [(1,1,2), (0,0,1), (0,1,0), (0,1,2), (1,4,0)] and you want to sort after the second tuple value first. But if there’s a tie (e.g. (0,1,0) and (1,1,2)), you want to sort after the third tuple value. If there’s another tie, you want to sort after the first tuple value. How can you do that?
Per default, Python sorts tuples lexicographically—the first tuple value is considered first. Only if there’s a tie, it takes the second tuple value and so on.
So to sort with “two keys”, you can define a key function that returns a tuple rather than only a single tuple value. Here’s an example:
>>> lst = [(1,1,2), (0,0,1), (0,1,0), (0,1,2), (1,4,0)] >>> lst.sort() >>> lst [(0, 0, 1), (0, 1, 0), (0, 1, 2), (1, 1, 2), (1, 4, 0)] >>> lst.sort(key=lambda x: (x[1],x[2],x[0])) >>> lst [(0, 0, 1), (0, 1, 0), (0, 1, 2), (1, 1, 2), (1, 4, 0)]
The second tuple value takes precedence over the third tuple value. And the third tuple value takes precedence over the first tuple value.
Python List Sort Lambda
Lambda functions are anonymous functions that are not defined in the namespace (they have no names). In it’s simplest form, the syntax is:
lambda argument : expression.
You map the argument to the result of the expression.
You can use the lambda function syntax to define the key argument of the sort() method in place.
Here’s an example:
>>> from operator import itemgetter
>>> customers = [('alice', 1000), ('bob', 100), ('frank', 10)]
>>> customers.sort(key=lambda x: x[1])
[('frank', 10), ('bob', 100), ('alice', 1000)]The lambda function returns the second tuple value of each tuple in the list. This is the basis on which the sorting algorithm bases its order.
Python List Sort with Comparator
In the previous examples, you’ve learned about the key argument that allows you to specify for each list element how it should be treated when sorting the list. This way, you can create a separate “value” for each element. The sort() method then sorts the list based on these “values” rather than based on the list elements themselves.
There’s only one condition: the returned values must be comparable. Otherwise, how’d you expect the list to sort them?
What does it mean to be comparable? And how do you make your own custom class comparable? To do this, you must implement a number of methods in your custom class definition (source):
| Operator | Method |
|---|---|
| == | __eq__ |
| != | __ne__ |
| < | __lt__ |
| <= | __le__ |
| > | __gt__ |
| >= | __ge__ |
If you implement all of those methods, you can compare two elements easily. All basic Python data structures have implemented them. So don’t worry about it.
Python List Sort Implementation
Python’s sorting routines such as list.sort() and the built-in sorted() use the Timsort algorithm (named after its creator Tim Peters).
The main idea is to use the popular mergesort algorithm that allows you to quickly combine two already sorted sequences quickly in linear runtime. So if you already have sorted subsequences, they can be combined quickly.
The Timsort algorithm exploits this idea by searching for already sorted subsequences that can be merged together (these sorted subsequences are called “runs” in the original algorithmic description of Timsort). If you can quickly identify runs and you can quickly merge those runs into a sorted sequence, you exploit the existing (random) ordering of the data. Many real-world data sets already come with many such sorted “runs”.
Thus, while the algorithm has the same worst-case time complexity of O(n log n), the best-case time complexity is O(n). In many practical settings, the algorithm outperforms theoretically similar algorithms because of the property of leveraging the existing ordering of the data.
You can dive deep into the Timsort algorithm here.
Python List Sort Complexity
Python’s Timsort algorithm has O(n log n) worst-case time complexity and O(n) best-case time complexity if the list is already largely sorted. It also has excellent benchmark results—it outperforms many of the best sorting algorithms in the world on real-world input data.
Python List Sort Error
There are two common errors when using the list.sort() method.
Python List Sort Returns None
The return value of the list.sort() method is None, but many coders expect it to be the sorted list. So they’re surprised finding out that their variables contain the None type rather than a sorted list.
>>> lst = [10, 5, 7] >>> a = lst.sort() >>> print(a) None
However, returning None makes perfect sense for the list.sort() method. Why? Because you call the method on a list object and it modifies this exact list object. It doesn’t create a new list—there won’t be a new list object in memory.
>>> print(lst) [5, 7, 10]
If you want to create a new list object, use the sorted() built-in Python function like this:
>>> sorted([10, 8, 9]) [8, 9, 10]
Python list sort ‘nonetype’ object is not iterable
Say you want to iterate over a list in a sorted order. You want to use the list.sort() method to accomplish this.
This code snippet would solve the problem, wouldn’t it?
years = [2008, 1999, 2012, 1988]
for year in years.sort():
print(year)But when running the code, you get the following error message:
Traceback (most recent call last):
File "C:\Users\xcent\Desktop\code.py", line 3, in <module>
for year in years.sort():
TypeError: 'NoneType' object is not iterableWhy does the TypeError occur?
The reason is that the list.sort() method returns the value None. It doesn’t return a new list with sorted values (as you expected). Instead, it sorts the list in place. If you want to fix this and get a new list with sorted values, you need to use the built-in sorted(list) method.
Here’s an example:
years = [2008, 1999, 2012, 1988]
for year in sorted(years):
print(year)Now, the result is expected:
1988 1999 2008 2012
Python List Sort Alphabetically/Lexicographically
Problem: Given a list of strings. Sort the list of strings in alphabetical order!
Example:
['Frank', 'Alice', 'Bob'] --> ['Alice', 'Bob', 'Frank']
Solution: Use the list.sort() method without argument to solve the list in lexicographical order which is a generalization of alphabetical order (also applies to the second, third, … characters).
lst = ['Frank', 'Alice', 'Bob'] lst.sort() print(lst) # ['Alice', 'Bob', 'Frank']
Try It Yourself:
Python List Sort Alphabetically Reverse
You can reverse the order of the list by using the reverse keyword. Set reverse=False to sort in ascending order and set reverse=True to sort in descending order.
lst = ['Frank', 'Alice', 'Bob'] lst.sort(reverse=False) print(lst) # ['Alice', 'Bob', 'Frank'] lst.sort(reverse=True) print(lst) # ['Frank', 'Bob', 'Alice']
Python List Sort Alphabetically and Numerically
Problem: You’ve got a list of strings. Each string contains a number. You want the numbers to sort numerically (e.g., 100 comes after 20, not before) but the characters to sort alphabetically (e.g., 'c' comes before 'd').
Example:
['alice 100', 'alice 20', 'bob 99'] --> ['alice 20', 'alice 100', 'bob 99'
Naive Solution (doesn’t work): Use the list.sort() method to sort the list alphabetically:
lst = ['alice 100', 'alice 20', 'bob 99'] lst.sort() print(lst) # ['alice 100', 'alice 20', 'bob 99']
Because the number 100 comes before 20 in an alphabetical order, the string 'alice 100' is placed before 'alice 20'.
Solution: I found this code on StackOverflow that nicely demonstrates how to sort alphanumerically:
import re
def sorted_nicely(l):
""" Sort the given iterable in the way that humans expect."""
convert = lambda text: int(text) if text.isdigit() else text
alphanum_key = lambda key: [convert(c) for c in re.split('([0-9]+)', key)]
l.sort(key = alphanum_key)
lst = ['alice 100', 'alice 20', 'bob 99']
sorted_nicely(lst)
print(lst)
# ['alice 20', 'alice 100', 'bob 99']The idea is to differentiate characters and numbers and use them as the basis of comparison for the sort routine.
Python Sort List with Letters and Numbers
See previous Section Python List Sort Alphabetically.
Python List Sort Case Insensitive
The problem with the default list.sort() or sorted(list) method is that they consider capitalization. This way, it can lead to strange sortings like this:
lst = ['ab', 'Ac', 'ad'] lst.sort() print(lst) # ['Ac', 'ab', 'ad']
Intuitively, you would expect the string 'ab' to occur before 'Ac', right?
To ignore the capitalization, you can simply call the x.lower() method on each element x before sorting the list.
However, my preferred method is to use the key argument to accomplish the same thing in a single line of code:
lst = ['ab', 'Ac', 'ad'] lst.sort(key=lambda x: x.lower()) print(lst) # ['ab', 'Ac', 'ad']
If you like one-liners, you’ll love my new book “Python One-Liners” with NoStarch Press (Amazon Link).
Python List Sort In Place
If you call the list.sort() method, you sort the list object in place. In other words, you don’t create a new list with the same elements in sorted order. No! You sort the existing list. Thus, all variables that also point to this list in memory will see the changed list.
Here’s an example that shows exactly that:
lst_1 = ['Bob', 'Alice', 'Frank'] lst_2 = lst_1 lst_1.sort() print(lst_2) # ['Alice', 'Bob', 'Frank']
You can see in the code that the sorting is visible for the variable lst_2 that point to the same object in memory.
If you want to sort the list but return a new object (without modifying the old list object), you need to take the Python built-in sorted() method:
lst_1 = ['Bob', 'Alice', 'Frank'] lst_2 = sorted(lst_1) print(lst_1) # ['Bob', 'Alice', 'Frank'] print(lst_2) # ['Alice', 'Bob', 'Frank']
Now both lists point to separate list objects in memory. Thus, the change in the order of the elements is only visible to list lst_2.
Python List Sort Ascending vs Descending (Reverse)
To sort a list in ascending order means that the elements are ordered from small to large. Per default, Python lists are sorted in ascending order.
lst_1 = ['Bob', 'Alice', 'Frank'] lst_1.sort() print(lst_1) # ['Alice', 'Bob', 'Frank'] lst_2 = [10, 8, 11, 2, 1] lst_2.sort() print(lst_2) # [1, 2, 8, 10, 11]
However, if you want to sort in descending order (from large to small), you can use either of the following two methods:
- Use the
list.sort(reverse=True)method with thereverse=Trueargument. - Use slicing
list[::-1]to reverse the order of the list.
The difference between both methods is that the first changes the list in place, and the second creates a new list with sorted elements in descending order.
Here’s the example:
lst_1 = ['Bob', 'Alice', 'Frank'] lst_1.sort(reverse=True) print(lst_1) # ['Frank', 'Bob', 'Alice'] lst_2 = [10, 8, 11, 2, 1] lst_2.sort() lst_2 = lst_2[::-1] print(lst_2) # [11, 10, 8, 2, 1]
As you see, using the reverse=True argument is prettier in most cases.
Python List Sort Index (Argsort)
What if you want to sort a list but you only want to have the indices of the sorted elements?
Problem: Say, you have the list ['Bob', 'Alice', 'Carl'] and you’re interested in the sorted indices [1, 0, 2].
Solution: There are many pure Python ways on the web, but the simplest and most efficient solution is to “stand on the shoulders of giants” and use the NumPy library—specifically, the np.argsort() method.
Here’s how:
import numpy as np lst = ['Bob', 'Alice', 'Carl'] sorted_indices = np.argsort(lst) print(sorted_indices) # [1 0 2]
Why look further than that? If you need the result to be a list, then feel free to convert it using the list(...) constructor.
Related article:
Python Sort List of Strings
How can you sort a list of strings? There’s no difference – just use the normal list.sort() method. If you need to sort in an alphanumerical way, then use the tips above (see Section Python List Sort Alphabetically).
Here’s the minimal example:
lst = ['Bob', 'Alice', 'Carl'] lst.sort() print(lst) # ['Alice', 'Bob', 'Carl']
Python Sort List of Floats
You can sort a list of floats like you sort any other list. There’s no difference:
lst = [101.0, 20.9, 13.4, 106.4] lst.sort() print(lst) # [13.4, 20.9, 101.0, 106.4]
The default sorting of numerical values is in ascending order.
However, what if you have the list of floats given as string values? This can lead to unexpected behavior:
lst = ['101.0', '20.9', '13.4', '106.4'] lst.sort() print(lst) # ['101.0', '106.4', '13.4', '20.9']
The “sorted” list looks strange. The problem is that the strings are sorted alphabetically, not numerically. The letter '1' comes before the letter '2' in the Unicode alphabet. That’s why the number '101.0' comes before '20.9'—even if the latter is a smaller numerical value.
If you want to sort the list numerically, you have to convert all list values to floats first. The easiest way to do this is to use the float() built-in Python conversion function as a key argument of the lst.sort() method.
lst = ['101.0', '20.9', '13.4', '106.4'] lst.sort(key=float) print(lst) # ['13.4', '20.9', '101.0', '106.4']
This way, you retain the string data type because the list values are not actually changed. But you associate a new “value” to each list element via the key function—the respective float value of the string element.
Python Sort List of Tuples
Problem: Say you have a list of tuples [(1,1,2), (0,0,1), (0,1,0), (0,1,2), (1,4,0)] and you want to sort after the second tuple value first. But if there’s a tie (e.g. (0,1,0) and (1,1,2)), you want to sort after the third tuple value. If there’s another tie, you want to sort after the first tuple value. How can you do that?
Per default, Python sorts tuples lexicographically which means that the first tuple value is considered first. Only if there’s a tie, it takes the second tuple value and so on.
Solution: Define a key function that returns a tuple rather than only a single tuple value. Here’s an example:
>>> lst = [(1,1,2), (0,0,1), (0,1,0), (0,1,2), (1,4,0)] >>> lst.sort() >>> lst [(0, 0, 1), (0, 1, 0), (0, 1, 2), (1, 1, 2), (1, 4, 0)] >>> lst.sort(key=lambda x: (x[1],x[2],x[0])) >>> lst [(0, 0, 1), (0, 1, 0), (0, 1, 2), (1, 1, 2), (1, 4, 0)]
The second tuple value takes precedence over the third tuple value. And the third tuple value takes precedence over the first tuple value.
Python Sort List of Dictionaries
Next, you’re going to learn how to sort a list of dictionaries in all possible variations. [1] So let’s get started!
How to Sort a List of Dictionaries By Value?
Problem: Given a list of dictionaries. Each dictionary consists of multiple (key, value) pairs. You want to sort them by value of a particular dictionary key (attribute). How do you sort this dictionary?
Minimal Example: Consider the following example where you want to sort a list of salary dictionaries by value of the key 'Alice'.
salaries = [{'Alice': 100000, 'Bob': 24000},
{'Alice': 121000, 'Bob': 48000},
{'Alice': 12000, 'Bob': 66000}]
sorted_salaries = # ... Sorting Magic Here ...
print(sorted_salaries)The output should look like this where the salary of Alice determines the order of the dictionaries:
[{'Alice': 12000, 'Bob': 66000},
{'Alice': 100000, 'Bob': 24000},
{'Alice': 121000, 'Bob': 48000}]Solution: You have two main ways to do this—both are based on defining the key function of Python’s sorting methods. The key function maps each list element (in our case a dictionary) to a single value that can be used as the basis of comparison.
- Use a lambda function as the key function to sort the list of dictionaries.
- Use the itemgetter function as the key function to sort the list of dictionaries.
Here’s the code of the first option using a lambda function that returns the value of the key 'Alice' from each dictionary:
# Create the dictionary of Bob's and Alice's salary data
salaries = [{'Alice': 100000, 'Bob': 24000},
{'Alice': 121000, 'Bob': 48000},
{'Alice': 12000, 'Bob': 66000}]
# Use the sorted() function with key argument to create a new dic.
# Each dictionary list element is "reduced" to the value stored for key 'Alice'
sorted_salaries = sorted(salaries, key=lambda d: d['Alice'])
# Print everything to the shell
print(sorted_salaries)The output is the sorted dictionary. Note that the first dictionary has the smallest salary of Alice and the third dictionary has the largest salary of Alice.
[{'Alice': 12000, 'Bob': 66000},
{'Alice': 100000, 'Bob': 24000},
{'Alice': 121000, 'Bob': 48000}]Try It Yourself:
You’ll learn about the second way below (where you use the itemgetter function from the operator module).
Related articles on the Finxter blog:
Python List Sort Remove Duplicates (Sort + Unique)
Idea: To remove duplicates from a list, you can sort the list first and then go over the list once and remove duplicates. As the list is sorted, duplicates will appear side by side. This makes it easier to spot them.
Runtime Complexity: Say, you’ve got a list [1, 10, 3, 2, 3, 1, 11, 10]. If you go over each element and check if this element exists at another position, the runtime complexity is O(n²) for n elements. But if you sort the list first, the runtime complexity is only O(n log n) for sorting. Going over the sorted list [1, 1, 2, 3, 3, 10, 10, 11] once more to find subsequent duplicates is only O(n) so overall runtime complexity of the sorted duplicate detection is O(n log n).
Solution: Consider the following code.
lst = [1, 10, 3, 2, 3, 1, 11, 10]
lst.sort()
index = 0
while index < len(lst) - 1:
if lst[index] == lst[index+1]:
lst.pop(index)
index = index + 1
print(lst)
# [1, 2, 3, 10, 11]Discussion: We keep track of the current index that goes from left to right over the list and removes an element if its successor in the list is a duplicate. This way, you remove all duplicates from the sorted list.
Alternatives: You can also convert the list to a set and back to a list to remove duplicates. This has runtime complexity of only O(n) and is, therefore, more efficient.
lst = [1, 10, 3, 2, 3, 1, 11, 10] dup_free = list(set(lst)) print(dup_free) # [1, 2, 3, 10, 11]
Python List Quicksort
Quicksort is not only a popular question in many code interviews – asked by Google, Facebook, and Amazon – but also a practical sorting algorithm that is fast, concise, and readable. Because of its beauty, you won’t find many “Intro to Algorithms” classes that don’t discuss the Quicksort algorithm.
Quicksort sorts a list by recursively dividing the big problem (sorting the list) into smaller problems (sorting two smaller lists) and combining the solutions from the smaller problems in a way that it solves the big problem. In order to solve each smaller problem, the same strategy is used recursively: the smaller problems are divided into even smaller subproblems, solved separately, and combined. Because of this strategy, Quicksort belongs to the class of “Divide and Conquer” algorithms. Let’s dive deeper into the Quicksort algorithm:
The main idea of Quicksort is to select a pivot element and then placing all elements that are larger or equal than the pivot element to the right and all elements that are smaller than the pivot element to the left. Now, you have divided the big problem of sorting the list into two smaller subproblems: sorting the right and the left partition of the list. What you do now is to repeat this procedure recursively until you obtain a list with zero elements. This list is already sorted, so the recursion terminates.
The following figure shows the Quicksort algorithm in action:
Figure: The Quicksort algorithm selects a pivot element, splits up the list into (i) an unsorted sublist with all elements that are smaller or equal than the pivot, and (ii) an unsorted sublist with all elements that are larger than the pivot. Next, the Quicksort algorithm is called recursively on the two unsorted sublists to sort them. As soon as the sublists contain maximally one element, they are sorted by definition – the recursion ends. At every recursion level, the three sublists (left, pivot, right) are concatenated before the resulting list is handed to the higher recursion level.
Here’s a Python one-liner implementation from my new Python One-Liners Book (Amazon Link).
## The Data unsorted = [33, 2, 3, 45, 6, 54, 33] ## The One-Liner q = lambda l: q([x for x in l[1:] if x <= l[0]]) + [l[0]] + q([x for x in l if x > l[0]]) if l else [] ## The Result print(q(unsorted))
If you need some explanation, check out my in-depth blog article about this one-liner Quicksort implementation:
Related articles:
Python List Sort Len
Problem: Given a list of strings. How can you sort them by length?
Example: You want to sort your list of strings ['aaaa', 'bbb', 'cc', 'd'] by length—starting with the shortest string. Thus, the result should be ['d', 'cc', 'bbb', 'aaaa']. How to achieve that?
Solution: Use the len() function as key argument of the list.sort() method like this: list.sort(key=len). As the len() function is a Python built-in function, you don’t need to import or define anything else.
Here’s the code solution:
lst = ['aaaa', 'bbb', 'cc', 'd'] lst.sort(key=len) print(lst)
The output is the list sorted by length of the string:
['d', 'cc', 'bbb', 'aaaa']
You can also use this technique to sort a list of lists by length.
Python List Sort Enumerate
Problem: Given an enumerated list of (index, value) pairs. How can you sort the list by value?
Example: You have the list ['Alice', 'Bob', 'Ann', ‘Frank’]. The enumerated list is list(enumerate(['Alice', 'Bob', 'Ann', 'Frank'])) == [(0, 'Alice'), (1, 'Bob'), (2, 'Ann'), (3, 'Frank')]. How can you sort that by value.
Solution: This is an instance of the problem: how to sort a list of tuples by the second tuple value? You can do this by using the key argument with a simple lambda function that returns the second tuple value as a basis for comparison.
Here’s the code solution:
lst = ['Alice', 'Bob', 'Ann', 'Frank'] en_lst = list(enumerate(lst)) en_lst.sort(key=lambda x: x[1]) print(en_lst)
The output is the list sorted by the value of the enumerated list.
[(0, 'Alice'), (2, 'Ann'), (1, 'Bob'), (3, 'Frank')]
Python List Sort Zip
Problem: How to sort a zipped list by values?
Example: Given two lists [5, 7, 9] and ['Alice', 'Bob', 'Ann']. Zip them together to obtain [(5, 'Alice'), (7, 'Bob'), (9, 'Ann')]. How to sort this list by value (i.e., the second tuple value).
Solution: Again, the solution is a variant of the problem: how to sort a list of tuples by second tuple value? You can do this by using the key argument with a simple lambda function that returns the second tuple value as a basis for comparison.
Here’s the code solution:
a = [5, 7, 9] b = ['Alice', 'Bob', 'Ann'] zipped = list(zip(a, b)) # [(5, 'Alice'), (7, 'Bob'), (9, 'Ann')] zipped.sort(key=lambda x: x[1]) print(zipped)
Here’s the output of the sorted zipped list:
[(5, 'Alice'), (9, 'Ann'), (7, 'Bob')]
Python List Sort Except First Element
Problem: How to sort a list except the first element? The first element should remain at the first position.
Example: Given a list [99, 3, 8, 1, 12]. After sorting, you want the almost sorted list [99, 1, 3, 8, 12]. Only the first element is ignored by the sorting routine.
Solution: You use the sorted(iterable) function to return a new list. As iterable to be sorted, you use all elements of the original list except the first one. Slicing helps you carve out this sublist. Then, you use list concatenation to glue together the sorted sublist and the first element of the list.
Here’s the code solution:
lst = [99, 3, 8, 1, 12] lst_2 = lst[:1] + sorted(lst[1:]) print(lst_2)
Here’s the output of the sorted zipped list:
[99, 1, 3, 8, 12]
Python List Sort File
Problem: Sort a file alphabetically, line by line.
Example: Say, you’ve got the following file "chat.txt" that contains some timestamps of messages in a chatroom.
2014-05-12: hi 2020-07-13: Python is great 2020-07-12: Is Python great? 2014-06-01: how are you?
You want the following sorted file/string:
2014-05-12: hi 2014-06-01: how are you? 2020-07-12: Is Python great? 2020-07-13: Python is great
How can you sort this file in Python?
Solution: You use a concise one-liner to load the contents of the file into a list of strings, one for each line. Then, you sort the list.
Here’s the code:
lines = [line for line in open('chat.txt')]
lines.sort()
print(lines)The output is the following sorted list:
['2014-05-12: hi\n', '2014-06-01: how are you?', '2020-07-12: Is Python great?\n', '2020-07-13: Python is great\n']
If you want to store the results in another file, you can simply write it in a new file. If you don’t need the trailing whitespace characters, you can call strip() like this:
lines = [line.strip() for line in open('chat.txt')]Python List Sort vs Sorted
What’s the difference between the list.sorted() method of Python lists and the sorted() built-in function? Given a list…
- The method
list.sort()sorts the given list in place. It doesn’t create a new list. - The Python built-in function
sorted()creates a new list object with sorted elements.
The return value of the list.sort() method is None but many coders expect it to be the sorted list. So they’re surprised finding out that their variables contain the None type rather than a sorted list.
>>> lst = [10, 5, 7] >>> a = lst.sort() >>> print(a) None
However, returning None makes perfect sense for the list.sort() method. Why? Because you call the method on a list object and it modifies this exact list object. It doesn’t create a new list—there won’t be a new list object in memory.
>>> print(lst) [5, 7, 10]
If you want to create a new list object, use the sorted() built-in Python function like this:
>>> sorted([10, 8, 9]) [8, 9, 10]
Python List Index Time Complexity
For simplicity, here’s the Python equivalent of the implementation with some basic simplifications that don’t change the overall complexity:
def index(value, lst):
for i, el in enumerate(lst):
if el==value:
return i
raise Exception('ValueError')
print(index(42, [1, 2, 42, 99]))
# 2
print(index("Alice", [1, 2, 3]))
'''
Traceback (most recent call last):
File "C:UsersxcentDesktopcode.py", line 10, in <module>
print(index("Alice", [1, 2, 3]))
File "C:UsersxcentDesktopcode.py", line 5, in index
raise Exception('ValueError')
Exception: ValueError
'''I know it’s not the perfect replication of the above C++ code. But it’s enough to see the computational (runtime) complexity of the list.index(value) method.
The index() method has linear runtime complexity in the number of list elements. For n elements, the runtime complexity is O(n) because in the worst case you need to iterate over each element in the list to find that the element does not appear in it.
Let’s check the runtime complexity practically for different list sizes with a short benchmark program.
You can see a plot of the time complexity of the index() method for growing list size here:
The figure shows how the elapsed time of finding the last list element in a list. This experiment is repeated for a growing number of elements. The runtime grows linear to the number of elements.
If you’re interested in the code I used to generate this plot with Matplotlib, this is it:
import matplotlib.pyplot as plt
import time
y = []
for i in [100000 * j for j in range(10,100)]:
lst = list(range(i))
t0 = time.time()
x = lst.count(-99)
t1 = time.time()
y.append(t1-t0)
plt.plot(y)
plt.xlabel("List elements (10**5)")
plt.ylabel("Time (sec)")
plt.show()
Related articles:
Python List sort() Thread Safe
Do you have multiple threads that access your list at the same time? Then you need to be sure that the list operations (such as sort()) are actually thread safe.
In other words: can you call the sort()
The answer is yes (if you use the cPython implementation). The reason is Python’s global interpreter lock that ensures that a thread that’s currently working on its code will first finish its current basic Python operation as defined by the cPython implementation. Only if it terminates with this operation will the next thread be able to access the computational resource. This is ensured with a sophisticated locking scheme by the cPython implementation.
The only thing you need to know is that each basic operation in the cPython implementation is atomic. It’s executed wholly and at once before any other thread has the chance to run on the same virtual engine. Therefore, there are no race conditions. An example of such a race condition would be the following: the first thread reads a value from the list, the second thread overwrites the value, and the first thread overwrites the value again invalidating the second thread’s operation.
All cPython operations are thread-safe. But if you combine those operations into higher-level functions, those are not generally thread safe as they consist of many (possibly interleaving) operations.
Where to Go From Here?
The list.sort() method sorts the list elements in place in an ascending manner. To customize the default sorting behavior, use the optional key argument by passing a function that returns a comparable value for each element in the list. With the optional Boolean reverse argument, you can switch from ascending (reverse=False) to descending order (reverse=True).
If you keep struggling with those basic Python commands and you feel stuck in your learning progress, I’ve got something for you: Python One-Liners (Amazon Link).
In the book, I’ll give you a thorough overview of critical computer science topics such as machine learning, regular expression, data science, NumPy, and Python basics—all in a single line of Python code!
OFFICIAL BOOK DESCRIPTION: Python One-Liners will show readers how to perform useful tasks with one line of Python code. Following a brief Python refresher, the book covers essential advanced topics like slicing, list comprehension, broadcasting, lambda functions, algorithms, regular expressions, neural networks, logistic regression and more. Each of the 50 book sections introduces a problem to solve, walks the reader through the skills necessary to solve that problem, then provides a concise one-liner Python solution with a detailed explanation.