Python, lesson 12
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(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 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.
lambdaThe operator module has ready-made key functions: itemgetter(1) does the same as the
lambda above, and attrgetter("score") reads an attribute from objects.
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:
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().
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, descendingfrom 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 <= 154
cleo 50
ana 70
ben 50
dev 901. dev 90
2. ana 70
3. ben 50
4. cleo 5095 59 60 89 70AFDBC