Sorting by a key
You have already sorted a few times in this course: sorted put the letters of a word in order, and it put a dictionary's keys in order. Both times the values were compared in their usual order: numbers from smallest to largest, and strings by character code, which for lowercase words is dictionary order.
Often you want a different order. A leaderboard lists players from the most wins to the fewest. A to-do list goes by deadline. A word game might want the shortest words first. The values are the same in each case; what changes is the rule for which one comes first. In this lesson you'll learn how to give the sort that rule, and then what a list in the right order lets you do: answer questions about repeated and nearby values in one pass, and choose the order in which to do a set of jobs.
Take four words, ['mango', 'fig', 'banana', 'pear'], that you want from shortest to longest. sorted(words) compares the words themselves, so it gives alphabetical order. You need it to compare their lengths instead. That is what a key is for: a function of one item that sorted calls once on each item. The items are then sorted by the values it returns. With key=len, the four words are sorted by the lengths 5, 3, 6 and 4.
sorted(items) returns a new sorted list and leaves items as it was, while items.sort() sorts the list itself. Both take a key, and reverse=True turns the order around, so that the longest words come first. This program sorts the words three ways:
Sorting words three ways
words = ['mango', 'fig', 'banana', 'pear']
print(sorted(words))
print(sorted(words, key=len))
print(sorted(words, key=len, reverse=True))Python details
key=len passes the function len itself, with no parentheses; sorted does the calling. A key can be any one-argument function: a built-in such as len, a function you wrote with def, or a lambda. Uppercase letters come before lowercase ones, and key=lambda w: w.lower() sorts words as if they were all lowercase.
Sorting from largest to smallest puts the largest items first, and this problem asks for the largest few:
Snuke has sticks, and the -th stick has length . He makes a toy by joining of the sticks, and the toy's length is the sum of their lengths. Print the largest possible length of the toy.
Constraints
Sample 1 · Input
5 3 1 2 3 4 5
Output
12
Sample 2 · Input
15 14 50 26 27 21 41 7 42 35 7 5 5 36 39 1 45
Output
386
In the first sample, 3 of the sticks 1 to 5 are chosen, and the best choice is the three longest, . That holds in general: replacing any chosen stick with a longer unchosen one makes the toy longer, so the answer is the sum of the longest sticks. Once the lengths are sorted from longest to shortest, those are the first .
Summing the K longest sticks
n, k = map(int, input().split())
lengths = list(map(int, input().split()))
lengths.sort(reverse=True)
print(sum(lengths[:k]))Python details
lengths[:k] is a slice holding the first k elements, and sum adds them.
Breaking ties with a second rule
Sorting by length raises a question the first example avoided: what happens when two words have the same length? Take pear, fig, kiwi, plum and apple. By length, fig comes first and apple last, but pear, kiwi and plum all have 4 letters.
Python's sort is stable: items that tie keep the order they had before the sort, so sorted(words, key=len) gives fig, pear, kiwi, plum, apple. Often you want a rule for ties instead, such as alphabetical order. Then the key returns a tuple, here (len(w), w). Tuples compare the way words do in a dictionary: by their first elements, and only when those are equal, by their second. So (3, 'fig') < (4, 'pear') because 3 is less than 4, and (4, 'kiwi') < (4, 'pear') because the lengths are equal and 'kiwi' < 'pear' decides.
Sorting words with a tie rule
words = ['pear', 'fig', 'kiwi', 'plum', 'apple']
print(sorted(words, key=len))
print(sorted(words, key=lambda w: (len(w), w)))Ranking players by wins
Here is a ranking problem that needs a second rule:
players, numbered 1 to , played a round-robin tournament, and every match had a winner. The results come as strings of length : the -th character of is o if player beat player , x if player lost to player , and - when .
A player with more wins ranks higher, and between two players with the same number of wins, the one with the smaller number ranks higher. Print the players' numbers from the highest rank to the lowest.
Constraints
- has length and consists of
o,xand-, in the format above
Sample 1 · Input
3 -xx o-x oo-
Output
3 2 1
Sample 2 · Input
7 -oxoxox x-xxxox oo-xoox xoo-ooo ooxx-ox xxxxx-x oooxoo-
Output
4 7 3 1 5 2 6
In the second sample, counting the os in each row gives the wins: players 1 to 7 have 3, 1, 4, 5, 3, 0 and 5. Players 4 and 7 tie with 5 wins, and 4 goes first because its number is smaller. Players 1 and 5 tie with 3 in the same way. So the order is 4, 7, 3, 1, 5, 2, 6.
This rule wants wins from high to low but numbers from low to high, so reverse=True won't do: it would reverse both. The usual way to flip one part of a key is to negate it. More wins give a smaller , so they come first, and the key for player is .
The answer is a list of player numbers, not wins, so the program sorts the indices and looks up each index's wins inside the key: lambda i: (-wins[i], i).
Sorting indices by a two-part rule
n = int(input())
wins = []
for i in range(n):
wins.append(input().count('o'))
order = sorted(range(n), key=lambda i: (-wins[i], i))
for i in order:
print(i + 1, end=' ')
print()Python details
Because Python's sort is stable and range(n) is already in increasing order, key=lambda i: -wins[i] alone would give the same order. Writing the tie rule into the key states the rule and does not depend on the input order.
The program prints i + 1 because the problem numbers players from 1 and the indices start at 0.
Scanning a sorted list
After a sort, the smallest items are at the front, the largest at the back, and each value sits next to the values closest to it in size. In particular, equal values sit next to each other. A question about repeated values or gaps between values then depends only on neighbors, and one pass over the sorted list answers it.
Counting the different values in a list shows the pattern. After sorting 6, 5, 6, 7, equal values form runs, 5 | 6 6 | 7, and every value that differs from the one before it starts a new run. So the number of different values is 1 plus the number of positions where a value differs from its left neighbor. Step through the scan below; the second preset leaves out the sort.
Step through a sorted scan
Without the sort, the scan on 3, 1, 3, 1, 3 prints 5: every value differs from its left neighbor, so every position looks like a new run, although the list holds only two different values. Sorted, the list is 1, 1, 3, 3, 3, and the scan finds one change, so it prints 2. The scan counts changes between neighbors, so it counts different values only when equal values are neighbors, and sorting puts them there.
For the count alone, a set is simpler: len(set(nums)). A sorted list also answers questions a set cannot, because values close in size end up next to each other. The two closest values in a list, for example, are neighbors after sorting. The list 31, 4, 17, 12, 25 sorts to 4, 12, 17, 25, 31, and comparing its 4 pairs of neighbors finds the smallest gap, , without checking all 10 pairs.
Counting runs and their lengths
This problem practices the scan. It asks for the number of runs and also for the length of the longest one:
Vasya has wooden bars of known lengths. A bar can be put on top of another only when the two have the same length. Using every bar, he builds as few towers as possible. Print the height of the tallest tower and the number of towers.
Constraints
- Every length is a natural number of at most 1000
Sample 1 · Input
3 1 2 3
Output
1 3
Sample 2 · Input
4 6 5 6 7
Output
2 3
Bars of equal length can all go in one tower, and bars of different lengths never share one, so each tower is one run of equal lengths. In the second sample the sorted lengths are 5 | 6 6 | 7: three towers, the tallest of height 2. The number of towers is the count from the demo. For the height, the program also keeps the length of the current run, restarts it at 1 whenever a new run begins, and remembers the largest value it reaches.
Runs and the longest run
n = int(input())
bars = sorted(map(int, input().split()))
towers = 1
run = 1
tallest = 1
for i in range(1, n):
if bars[i] == bars[i - 1]:
run += 1
else:
towers += 1
run = 1
tallest = max(tallest, run)
print(tallest, towers)Python details
sorted accepts the values map produces and returns them as a sorted list, so the program does not need list(...).
Sorting to choose an order
Some problems leave the order up to you. Say you have several jobs, each taking some time and due by a deadline, and you can work on only one at a time. Is there an order that finishes every job on time? Trying every order is hopeless: 20 jobs already have orders.
The one order you need to try is earliest deadline first. To see why it is enough, take any order that finishes everything in time, and suppose it does some job right before a job whose deadline is earlier. Swapping the two makes finish sooner than before, and finish at the moment used to finish. That moment was at or before 's deadline, so it is also before 's later one. Every other job finishes at the same time as before.
Swapping such neighbors again and again turns any order that works into an earliest-deadline order, so if an earliest-deadline order makes a job late, no order works. A program only has to sort the jobs by deadline, add up their times as it goes, and check each finish time against that job's deadline. This problem asks exactly that question:
Starting at time 0, Kizahashi has jobs. Job takes units of time and must be finished at or before time . He works on one job at a time and can start the next as soon as one is done. Print Yes if he can finish every job in time, and No otherwise.
Constraints
Sample 1 · Input
5 2 4 1 9 1 8 4 9 3 12
Output
Yes
Sample 2 · Input
3 334 1000 334 1000 334 1000
Output
No
Write each job as (time, deadline). In the first sample, sorted by deadline, the jobs are (2, 4), (1, 8), (1, 9), (4, 9) and (3, 12). Done in that order, they finish at times 2, 3, 4, 8 and 11, and each of those is at or before its deadline, so the answer is Yes. In the second sample, three jobs of 334 units all due at 1000 need 1002 units in total, so the last one is late whatever the order.
Earliest deadline first
n = int(input())
jobs = []
for i in range(n):
a, b = map(int, input().split())
jobs.append((a, b))
jobs.sort(key=lambda job: job[1])
finish = 0
answer = 'Yes'
for a, b in jobs:
finish += a
if finish > b:
answer = 'No'
break
print(answer)Python details
Each job is a (time, deadline) tuple, and key=lambda job: job[1] sorts the jobs by their deadline. finish is the moment the current job ends.
The cost of sorting
A natural way to sort by hand is to find the smallest item, put it first, and repeat on the rest. This method is selection sort. Finding the smallest of items takes comparisons, the next takes , and so on, so the total is
The library sort does far fewer comparisons: about . For , a common limit:
Python runs about simple steps a second. The library sort does its comparisons inside the interpreter's own compiled code and finishes in a fraction of a second, while selection sort written in Python would need about seconds.
With a time limit of a second or two, the library sort finishes with time to spare and selection sort does not come close, and the gap widens as grows.
| Selection sort at a second | |||
|---|---|---|---|
| 1,000 | 0.005 s | ||
| 50 s | |||
| 200 s |
Merge sort: halving and merging
One method that reaches is merge sort, which uses recursion: split the list in half, sort each half, then merge the two sorted halves by repeatedly taking the smaller of their two front items. Halving 8 items reaches single items after levels, and merging all the lists on one level takes about comparisons, so the total is about . The call tree below sorts eight numbers.
You do not need to write merge sort to use sorting; sorted and list.sort already do the work. The DSA roadmap's Sorting and selection lesson covers how library sorts work and when other methods beat them.
Common mistakes
Calling the key instead of passing it:
sorted(words, key=len()).- Where it breaks
len()is evaluated beforesortedstarts, and with no argument it raisesTypeError: len() takes exactly one argument (0 given). The key must be the function itself, whichsortedthen calls on each item.- The fix
- Pass the name with no parentheses:
key=len.
Writing
words = words.sort()in Python.- Where it breaks
list.sort()sorts in place and returnsNone, so afterwardswordsisNoneand the nextwords[0]raises aTypeError.- The fix
- Either call
words.sort()on its own line, or writewords = sorted(words).
Sorting numbers that are still strings, as in Python's
sorted(input().split()).- Where it breaks
- On the input
10 9 2this gives['10', '2', '9'], because strings compare character by character and'1'comes before'2'. Sorting a C++vector<string>of the same input gives the same order. - The fix
- Convert before sorting:
sorted(map(int, input().split()))in Python, or read the values into avector<int>in C++.
Reversing a whole two-part order to put one part from high to low:
key=lambda i: (wins[i], i)withreverse=Truein Python, or sorting(wins, number)pairs withgreaterin C++.- Where it breaks
- Reversing flips the tie rule as well. On the tournament's second sample, players 4 and 7 tie on 5 wins, and the reversed order puts 7 first:
7 4 3 5 1 2 6instead of4 7 3 1 5 2 6. - The fix
- Flip only the wins: negate them in the key,
(-wins[i], i), or compare them with>in the comparator.
Recall What does `sorted(['bb', 'a', 'ccc'], key=len, reverse=True)` return, and how many times does it call `len`?
['ccc', 'bb', 'a']. The key is called once per item, so len runs three times; the sort then compares the lengths 2, 1 and 3.
Recall Pairs are `(name, score)`. What key sorts them by score from high to low, and by name in alphabetical order when scores tie?
key=lambda p: (-p[1], p[0]). The negated score puts higher scores first, and the name breaks ties because tuples compare their second elements only when the first are equal.
Key terms
| Term | Meaning |
|---|---|
| key function | In Python, a function called once on each item; the items are sorted by what it returns. |
| comparator | In C++, a function of two items that returns true when the first must come before the second. |
| stable sort | A sort that keeps tied items in their original order: Python's, and C++'s stable_sort. |
| earliest deadline first | Doing jobs in order of their deadlines, which finishes every job in time whenever any order does. |
| selection sort | Sorting by finding the smallest item, putting it first and repeating on the rest: about comparisons. |
| merge sort | Sorting by sorting each half and merging the two sorted halves: about comparisons. |
