Module 5: Sorting and Dictionaries
Exercise
If you have not already, get prepared for class by downloading the start code:
!wget [Link]
Discuss the previous module with your neighbour.
What are the differences between a list and a tuple?
What are some of the methods that we saw on lists and strings?
What can we do with a range object?
1/28 CS 114 - Fall 2023 Module 5
Sorting
Quick! Is 7256 in this list?
[5421, 4448, 8635, 2444, 3711, 3477, 4367, 1793, 5484, 2508, 9668, 3643, 4257, 9226,
6525, 2511, 6087, 6259, 3256, 1205, 7471, 4749, 7247, 7699, 5423, 4845, 4860, 6055]
Now I have similar data, but sorted in increasing order. Is 7256 in this list?
[1041, 1952, 2385, 4743, 4896, 5008, 5081, 5417, 5555, 5612, 5896, 5960, 6278, 6294,
6391, 6864, 7196, 7339, 7428, 7451, 7624, 7741, 8240, 8461, 9098, 9164, 9408, 9607]
In the first case, you have to look at each item, one by one.
You can’t be sure until you look at every item.
In the second case, as soon as you look at the 6318 you can see that it can’t be in first row.
You can then quickly discard the second half of the second row, and so on.
After looking at only a handful of values we can be confident it’s not there.
Data can be much easier to work with if it ordered in some sensible way.
We want to learn to use tools that sort data.
2/28 CS 114 - Fall 2023 Module 5, Section 1: Sorting
Sorting Algorithms
There are many interesting sorting algorithms.
To see some antique algorithms, with 1981 computer graphics, I encourage you to watch
Sorting Out Sorting on YouTube.
It’s fun to think about sorting algorithms, and creating new ones is an active area of
research.
By default, Python uses a fairly new (2002) algorithm, Timsort, by Tim Peters.
But we don’t want to think about clever algorithms; we want to Do Science.
So we’ll let people like Tim create clever algorithms, and we’ll just use them.
3/28 CS 114 - Fall 2023 Module 5, Section 1: Sorting
Sorting tools: the sorted function
The built-in function sorted takes any iterable (a list, a str, or something else), and
returns a new list containing the same values, in sorted order.
## A list:
sorted([2,4,6,0,1]) ⇒ [0, 1, 2, 4, 6]
## A tuple gets turned into a list:
sorted(('In', 'a', 'hole', 'in', 'the', 'ground', 'there', 'lived', 'a', 'hobbit'))
⇒ ['In', 'a', 'a', 'ground', 'hobbit', 'hole', 'in', 'lived', 'the', 'there']
## A str is an iterable containing single characters; it's turned into a list:
sorted("Gandalf") ⇒ ['G', 'a', 'a', 'd', 'f', 'l', 'n']
## (The uppercase letters come before lowercase.)
sorted("Gandalf", reverse=True) ⇒ ['n', 'l', 'f', 'd', 'a', 'a', 'G']
It’s important to note: sorted never mutates a list. It returns a new list with the
!
values.
4/28 CS 114 - Fall 2023 Module 5, Section 1: Sorting
The [Link] method
On an existing list, we can call the [Link] method. This mutates the list and returns
None.
jvj = [2, 4, 6, 0, 1]
[Link]() ⇒ None
jvj ⇒ [0, 1, 2, 4, 6]
gloin = ['He', 'looks', 'more', 'like', 'a', 'grocer', 'than', 'a', 'burglar!']
[Link]() ⇒ None
gloin ⇒ ['He', 'a', 'a', 'burglar!', 'grocer', 'like', 'looks', 'more', 'than']
You can only call the [Link] method on a list; it won’t work on a str, tuple, etc, etc.
! It’s important to note: [Link] always returns None. It only mutates the list!
5/28 CS 114 - Fall 2023 Module 5, Section 1: Sorting
What kinds of things can we sort?
Both tools, sorted and [Link], work only when the items can be compared using the <
operator (or other similar operators). If we try: sorted([3, "Bilbo"]) we get an error:
TypeError: '<' not supported between instances of 'str' and 'int'
Which is smaller: 3, or "Bilbo"? It’s not clear what that would mean, so it’s an error.
But we can compare a lot of things using <.
We can compare two lists that contain comparable values: [2,6,5] < [3] ⇒ True.
So we can sort a list[list[int]]:
lol = [[3,7,4], [3,6], [1,8,5], [6], []]
sorted(lol) ⇒ [[], [1, 8, 5], [3, 6], [3, 7, 4], [6]]
6/28 CS 114 - Fall 2023 Module 5, Section 1: Sorting
Read The Fine Manual
Let’s read the documentation:
>>> help(sorted)
Help on built-in function sorted in module builtins:
sorted(iterable, /, *, key=None, reverse=False)
Return a new list containing all items from the iterable in ascending order.
A custom key function can be supplied to customize the sort order, and the
reverse flag can be set to request the result in descending order.
A flag is a parameter that is a bool.
If we set reverse=True, it will sort backwards:
sorted([2,4,6,0,1]) ⇒ [0, 1, 2, 4, 6]
sorted([2,4,6,0,1], reverse=True) ⇒ [6, 4, 2, 1, 0]
sorted("Gandalf") ⇒ ['G', 'a', 'a', 'd', 'f', 'l', 'n']
sorted("Gandalf", reverse=True) ⇒ ['n', 'l', 'f', 'd', 'a', 'a', 'G']
7/28 CS 114 - Fall 2023 Module 5, Section 1: Sorting
Sort keys
The help says: “A custom key function can be supplied to customize the sort order.”
This means we can write something like sorted(mylist, key=f), or [Link](key=f).
key is an optional named parameter that is a callable.
The system transforms each item using key, then puts the original values in order so that
these transformed values are sorted. E.g.: sort a list[str] using len as the key:
sorted(['cabbage', 'pear', 'avocado', 'dulse', 'mango', 'banana'], key=len)
'cabbage' 'pear' 'avocado' 'dulse' 'mango' 'banana'
7 4 7 5 5 6
Rearrange so lengths are ordered:
'pear' 'dulse' 'mango' 'banana' 'cabbage' 'avocado'
4 5 5 6 7 7
⇒ ['pear', 'dulse', 'mango', 'banana', 'cabbage', 'avocado']
Sort keys
Suppose we want to sort by units digit. For example, in 245, the units digit is 5; in 24601,
the units digit is 1. Since 1 < 5, once sorted 24601 should come somewhere before 245.
First step: write the key function.
Write a function units_digit(n:int) -> int, that returns the units digit n.
Exercise
[Link]("UD245", units_digit(245), 5)
[Link]("UD24601", units_digit(24601), 1)
[Link]("UD42", units_digit(42), 2)
(Work with non-negative integers for now, or test negatives carefully.)
That’s all we need. Now write: sorted([42, 245, 12, 7, 24601], key=units_digit)
⇒ [24601, 42, 12, 245, 7]
## Or...
mylist = [42, 245, 12, 7, 24601]
[Link](key=units_digit) ⇒ None
mylist ⇒ [24601, 42, 12, 245, 7]
Example: sorting tuples
Here are some values:
harry = ("Potter, Harry", 1980, ["Elder Wand", "Resurrection Stone", "Invis. Cloak"])
hermione = ("Granger, Hermione", 1979, ["Time Turner"])
frodo = ("Baggins, Frodo", 2968, ["One Ring", "Sting"])
sam = ("Gamgee, Samwise", 2980, [])
heroes = [harry, hermione, frodo, sam]
Write a function sort_by_item_count(characters: list[tuple[str, int, list[str]]]). It
mutates characters, so it is in increasing order by number of magical items.
Exercise
For example, sort_by_item_count(heroes) mutates so that heroes
⇒ [('Gamgee, Samwise', 2980, []),
('Granger, Hermione', 1979, ['Time Turner']),
('Baggins, Frodo', 2968, ['One Ring', 'Sting']),
('Potter, Harry', 1980, ['Elder Wand', 'Resurrection Stone', 'Invis. Cloak'])]
Remember, you just need to write a helper function that turns harry into 3, hermione
Hint
into 1, and so on. Then use [Link].
Stable sorting
Earlier we used key=len to sort foods:
sorted(['cabbage', 'pear', 'avocado', 'dulse', 'mango', 'banana'], key=len)
⇒ ['pear', 'dulse', 'mango', 'banana', 'cabbage', 'avocado']
Why does 'dulse' come before 'mango'? Why does 'cabbage' come before 'avocado'?
Answer: our sorting is stable. That means that items that are “equal” stay in the same
order.
Since len('dulse') and len('mango') are equal, these words stay in the same order after
sorting.
This means that if we first sort by “X”, and then sort by “Y”:
“Y” will define the groups
“X” will define the sorting within the groups.
half = sorted(['cabbage', 'pear', 'avocado', 'dulse', 'mango', 'banana'])
half ⇒ ['avocado', 'banana', 'cabbage', 'dulse', 'mango', 'pear'] # alphabetically
sorted(half, key=len)
⇒ ['pear', 'dulse', 'mango', 'banana', 'avocado', 'cabbage'] # by length
Stable sorting
The [Link] method can be used to determine how many times a letter appears:
w = 'constitutionality'; [Link]('t') ⇒ 4
w = 'floccinaucinihilipilifications'; [Link]('i') ⇒ 9
Write a function sort_q_count that takes a list[str] and returns a new list containing
the same words, categorized by how many times the letter 'q' appears, and sorted
alphabetically within each category.
Exercise
sort_q_count(['quote', 'dog', 'cat', 'albuquerque','saqqara','elephant',
'quinquereme', 'unique', 'clique'])
⇒ ['cat', 'dog', 'elephant',
'clique', 'quote', 'unique',
'albuquerque', 'quinquereme', 'saqqara']
13/28 CS 114 - Fall 2023 Module 5, Section 1: Sorting
Associating values with keys
We have two ways to usefully extract information from lists:
1 Use a for loop to walk through the list, one item at a time;
2 use an index to extract the value in a particular location.
Suppose now that I want to store a certain amount of information, indexed by a key.
For example, we want to associate an int represting a student ID with a tuple[str,str]
containing that student’s name and program. Some example data:
6938 with ("Al Gore", "government")
7334 with ("Bill Gates", "appliedmath")
8535 with ("Conan O'Brien", "history")
8838 with ("Barack Obama", "law")
14/28 CS 114 - Fall 2023 Module 5, Section 2: Dictionaries
Mostly empty list?
We could do this using a list.
Write None, (or some other value) to indicate “there is no student with this ID”:
6938 copies...
z }| {
students = [ None, None, ..., None ,("Al Gore", "government"),
None, None, ..., None ,("Bill Gates", "appliedmath"), None, None, ...]
| {z }
395 copies...
This does work, kind of. I can get: students[6938] ⇒ ("Al Gore", "government")
students[7334] ⇒ ("Bill Gates", "appliedmath")
But this in not very elegant. And if we wanted 8-digit student ID numbers, we would store
millions of empty values just to represent a few hundred thousand students.
This is definitely not a good way to store this kind of information.
!
There must be a better way, and there is: dictionaries.
15/28 CS 114 - Fall 2023 Module 5, Section 2: Dictionaries
Creating Dictionaries
A dictionary is a way to associate keys and values.
To create a dictionary, inside curly brackets {}, write key : value pairs, separated by a
comma.
For example:
students = {
6938: ("Al Gore", "government"),
7334: ("Bill Gates", "appliedmath"),
8535: ("Conan O'Brien", "history"),
8838: ("Barack Obama", "law")
}
The empty dictionary is expressed as {}.
16/28 CS 114 - Fall 2023 Module 5, Section 2: Dictionaries
Extracting Data from Dictionaries
We have the same two ways to get values from a dictionary:
1 By index, using a key as index:
students[6938] ⇒ ('Al Gore', 'government')
students[7334] ⇒ ('Bill Gates', 'appliedmath')
2 Using a for loop, we can iterate through the keys only:
for uw_id in students:
print(uw_id)
## This prints:
6938
7334
8535
8838
To see the associated values, use indexing on the keys:
for uw_id in students:
print(students[uw_id])
Annotating Dictionaries
With a list, the values in the list could have any type, but the index was always an int.
Using a dictionary, the values can still be any type, but the keys don’t have to be ints.
To annotate a dictionary we write dict[KeyType, ValueType], where KeyType and ValueType
represent the types of the keys and values.
Examples:
a = {3: 'trois', 4: 'quatre', 5: 'cinq'} is a dict[int, str]. Use: a[3] ⇒ 'trois'
b = {'trois': 3, 'quatre': 4, 'cinq': 5} is a dict[str, int]. Use: b['trois'] ⇒ 3
c = {(3, 4): 5.0,
(1, 1): 1.4141,
(2, 3): 3.606
}
Each key is a tuple[int, int], and each value is a float.
So this is a dict[tuple[int, int], float]. Use: c[(2,3)] ⇒ 3.606
18/28 CS 114 - Fall 2023 Module 5, Section 2: Dictionaries
Key types
Many types can be used as keys, including int, but also float, and str. We can even use
a tuple as a key, provided it contains only types that can themselves be used as keys.
Using only int and str as keys will be enough for the majority of our code. Be aware that
other types can be used.
We can’t use lists as keys; what can we use? Technically the only restriction is that the
type be hashable. We’re not going to go into what that means. If we want to say “the keys
can be anything, as far as possible”, we will use any, even though it’s slightly imprecise.
Consider:
crazydict = {[Link]: "cosine",
Exercise
[Link]: "sine",
abs: "absolute value"
}
What type is crazydict ?
Keys and Values
Here is a example dict[int, int]:
data = {4: 41,
9: 39,
3: 32,
2: 25}
We will write two functions that take such a value and return an int.
Write a function sum_keys that returns the Write a function sum_values that returns
Exercise
Exercise
sum of the keys: the sum of the values:
[Link]("SK", sum_keys(data), [Link]("SV", sum_values(data),
4 + 9 + 3 + 2) 41 + 39 + 32 + 25)
20/28 CS 114 - Fall 2023 Module 5, Section 2: Dictionaries
Mutating dictionaries
Like lists, we can add,change, and remove items from a dictionary.
Suppose we have:
a = {3: 'trois', 4: 'quatre', 5: 'cinq'}.
To add a new item, assign a new value using a new key as index:
a[24601] = 'Jean Valjean'
Now a is: {3: 'trois', 4: 'quatre', 5: 'cinq', 24601: 'Jean Valjean'}.
To change an item, assign a new value, using a key that is already in the dictionary:
a[24601] = 'Monsieur Madeleine'
Now a is: {3: 'trois', 4: 'quatre', 5: 'cinq', 24601: 'Monsieur Madeleine'}.
To remove a particular key : value pair, use the [Link] method, using an existing
key:
[Link](4)
Now a is: {3: 'trois', 5: 'cinq', 24601: 'Monsieur Madeleine'}.
21/28 CS 114 - Fall 2023 Module 5, Section 2: Dictionaries
Example: Reversing a dictionary
Write a function reverse_dictionary that takes a dict[int, str] and returns a new
Exercise
dict[str, int] that has keys and values reversed.
For example:
reverse_dict({ 3: 'trois', 4: 'quatre', 5: 'cinq' })
⇒ { 'trois': 3, 'quatre': 4, 'cinq': 5 }
Ex.
Can you find a dictionary d such that reverse_dict(reverse_dict(d)) != d ?
Notice: it’s impossible for a nats = {
dictionary to have the same key 0: 'zero',
more than once. 1: 'one',
2: 'prime',
3: 'prime',
But the same value can appear as 4: 'composite',
many times as you like: 5: 'prime',
6: 'composite',
}
Checking if a value is a key
With a list, we can us the in operator to check if something appears:
4 in [2, 4, 6, 0, 1] ⇒ True 3 in [2, 4, 6, 0, 1] ⇒ False
We can do the same with a dictionary, but it only checks the keys:
nats = {
0: 'zero', 3 in nats ⇒ True
1: 'one', 'prime' in nats ⇒ False
2: 'prime',
3: 'prime',
4: 'composite',
5: 'prime',
6: 'composite',
}
Exercise
Write a function contains(d: dict[any, any], target: any) -> bool that determines if
any value in d is equal to target. E.g.
contains(nats, 'prime') ⇒ True contains(nats, 'Optimus Prime') ⇒ False
Example: a Histogram
To count how many times each value appears in an iterable, consider the following
function:
def histogram(s: str) -> dict[str, int]:
"""Return a dictionary that counts how often each character appears in s."""
d = {}
for c in s:
if c not in d:
d[c] = 1
else:
d[c] = d[c] + 1
return d
h = histogram('brontosaurus')
Ex.
Carefully consider a trace of this call to histogram.
25/28 CS 114 - Fall 2023 Module 5, Section 2: Dictionaries
Module summary
Work with tuples, which behave like immutable lists.
Use range objects to count.
Use loops inside loops.
Use the built-in sorting tools (sorted and [Link]) to sort values, including the
reverse= flag and key= parameter.
Create and mutate dictionaries, iterate through them, check if items are present as
keys.
Before we begin the next module:
Read and complete the exercises in module 5 of the online textbook, at
[Link]
Complete the module 5 Review Quiz, due on Monday.
26/28 CS 114 - Fall 2023 Module 5, Section 3: Summary
Extra Practice
Write a function divisors(n). It returns a list containing all the positive integers that n
Exercise
is divisible by. For example,
[Link]("D10", divisors(10), [1,2,5,10])
[Link]("D7", divisors(7), [1,7])
(Hint: do not use a dictionary for this exercise. It won’t help.)
Exercise
Write a function divisor_dict(n). It takes positive int, and returns a
dict[int, list[int]], where the keys are the numbers from 1 to n, and the associated
value is a list containing all the numbers that divide that number.
27/28 CS 114 - Fall 2023 Module 5, Section 3: Summary
Extra Practice
Recall the Collatz sequence: if n is a number in the sequence, the next number is given by
n/2 when n is even, and by 3n + 1 when n is odd. Recall that this sequence always
seems to reach 1.
Write a function collatz_dict(n). It returns a dict[int,int] where each key is a value
in the Collatz sequence, and the value is the next value in the sequence. It should
Exercise
contain all the values encountered when starting at n. For example:
[Link]("C8", collatz_dict(8), {8:4, 4: 2, 2: 1})
[Link]("C3", collatz_dict(3),
{3: 10, 10: 5, 5: 16, 16: 8, 8: 4, 4: 2, 2: 1})