Learn/Python/12. Sorting and searching
Lesson 12 of 15
Sign in

Python, lesson 12

Sorting and searching

Sorting is one of the most common jobs a program does: leaderboards, alphabetical lists, "cheapest first". Python's sort is fast, stable and easy to customise, so you will almost never write your own.

sorted() and list.sort()

  • sorted(anything) returns a new list and works on any iterable: lists, tuples, strings, dictionary keys.
  • my_list.sort() sorts a list in place and returns None.

Both take the same two keyword arguments, key and reverse.

Key functions

key is a function that Python calls once on every item. The items are then ordered by those results instead of by themselves. You can pass any function, including a short :

2 exercises to try what you just read.

Exercise 1

Leaderboard

Press Ctrl Enter or Check to test your code.

Exercise 2

Grade bands

Press Ctrl Enter or Check to test your code.

lambda

The operator module has ready-made key functions: itemgetter(1) does the same as the lambda above, and attrgetter("score") reads an attribute from objects.

Sorting by more than one thing

Tuples compare item by item, so a key that returns a tuple sorts by the first part, then breaks ties with the second:

Negating a number flips its direction. That trick doesn't work for strings, but there's another way: Python's sort is stable, meaning items that compare equal keep their original order. So you can sort in several passes, least important key first:

Searching

For a small or unsorted list, in and list.index() simply look at each item in turn. That's a linear search, fine for hundreds of items, slow for millions.

If the data is sorted, binary search is much faster: look at the middle item, then throw away the half that can't contain the target, and repeat. A million items take only about twenty steps.

The bisect module does binary search for you on a sorted list:

  • bisect_left(a, x) returns the first position where x could be inserted while keeping a sorted, which is before any equal items.
  • bisect_right(a, x) returns the position after any equal items.
  • insort(a, x) inserts x in the right place.

bisect_right is also great for looking up ranges. Put the boundaries in a sorted list, and the position it returns tells you which bracket a value falls into.

Since Python 3.10 the bisect functions also accept a key= argument, just like sorted().

Further reading

  • Sorting techniques (HOWTO)
  • bisect module
  • operator.itemgetter

The first line is n, the number of players. Each of the next n lines holds a name and a score. Print the players ranked by score from highest to lowest; players with the same score appear in alphabetical order. Each output line is rank. name score, where rank starts at 1.

Sample input:

Sample output:

Grades use these boundaries: below 60 is F, 60–69 is D, 70–79 is C, 80–89 is B, 90 and above is A. Use bisect_right with the sorted boundary list [60, 70, 80, 90] and the string "FDCBA" to look up each grade, instead of a chain of if statements.

Input: one line of whole-number scores separated by spaces. Output: the matching letters on one line, with no spaces between them.

Sample input:

Sample output:

names = ["mia", "Zoe", "adam"]
print(sorted(names))                    # ['Zoe', 'adam', 'mia']  uppercase sorts first
print(sorted(names, key=str.lower))     # ['adam', 'mia', 'Zoe']
print(sorted(names, key=len, reverse=True))
players = [("ana", 30), ("ben", 45), ("cy", 30)]
by_score = sorted(players, key=lambda p: p[1])
# score from high to low, then name from A to Z
ranked = sorted(players, key=lambda p: (-p[1], p[0]))
step1 = sorted(players, key=lambda p: p[0])                  # by name
step2 = sorted(step1, key=lambda p: p[1], reverse=True)       # then by score, descending
from bisect import bisect_left, bisect_right

ages = [12, 15, 15, 18, 21]
i = bisect_left(ages, 15)
print(i, i < len(ages) and ages[i] == 15)   # 1 True: found at index 1
print(bisect_right(ages, 15))               # 3: number of items <= 15
4
cleo 50
ana 70
ben 50
dev 90
1. dev 90
2. ana 70
3. ben 50
4. cleo 50
95 59 60 89 70
AFDBC