Chapter 5 · Real programs
Practice: searching, sorting and testing
Step 1 of 20 · Demo
Linear search looks at each item
By the end of this lesson you can search and sort by hand, and test with assert.
A linear search looks at each item in turn; return in the loop ends the function at once.
Run it. Each print shows a look. The search for 9 stops at the first 9; the one for 5 returns -1.
Step 2 of 20 · Try it
Try it: find a name
Run it: every search gives -1, because "alan" is not "Alan". Make find ignore capitals: compare both sides in
small letters. The program must then print:
1
2
-1
lower() gives text in small letters (lesson 9). Put it on both sides of the ==.
Step 3 of 20 · Concept
assert checks your function
assert takes a condition. When it is True, nothing happens. When it is False, the program stops with an
AssertionError, and the traceback points at that assert.
A message after a comma ends up in the error's last line:
assert 2 + 2 == 5, "math is broken"
AssertionError: math is broken
A test is a function of asserts, each a case whose answer you know:
def test_find():
assert find([7, 3, 9, 4, 9], 9) == 2
assert find([7, 3, 9], 5) == -1
assert find([], 1) == -1
Step 4 of 20 · Demo
Tests that pass
Run it: every assert is True, so all tests passed prints. Now change the first assert's 2 into 3. Run it
again: an AssertionError, and the traceback names that assert's line.
Step 5 of 20 · Try it
Try it: bugs the tests catch
count_vowels has two small bugs. Run it and read which assert fails. Fix that bug, run it again, and fix the next.
When it prints all tests passed, you are done. Change only count_vowels, never the tests.
For "python" it gives 0: a return inside the loop ends the function in the first round. For "Ada", its A is a capital.
Step 6 of 20 · Concept
Binary search halves the list
In a sorted list, one look at the middle rules out half of it. Binary search keeps two indices, lo and hi:
the first and last place the target can still be.
mid = (lo + hi) // 2is the middle.- If
xs[mid]is the target, returnmid. - If it is smaller, the target comes after it:
lo = mid + 1. Elsehi = mid - 1. - Repeat while
lo <= hi. Oncelopasseshi, return-1.
Step 7 of 20 · Trace
Watch lo, mid and hi
xs, target, lo, hi and mid are names in the frame of bsearch (lesson 7). Press Next to follow a search
for 23.
def bsearch(xs, target):
lo = 0
hi = len(xs) - 1
while lo <= hi:
mid = (lo + hi) // 2
if xs[mid] == target:
return mid
elif xs[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
nums = [3, 8, 12, 15, 23, 31, 40, 47]
print(bsearch(nums, 23))bsearch(nums, 23)starts: 23 can be anywhere fromlo0 tohi7. Line 4 is next.- Line 5 made
mid(0 + 7) // 2 = 3. Line 6 comparesxs[3], 15, with 23. - 15 is too small, so line 9 made
lo4: 23 can only be after the middle. - Line 5 made
mid(4 + 7) // 2 = 5. Line 6 comparesxs[5], 31, with 23. - 31 is too big, so line 11 made
hi4. Only one place is left. - Line 5 made
mid4. Line 6 finds thatxs[4]is 23. - Line 7 returned 4 after three rounds. The frame of
bsearchis gone;printgets the 4. - Line 15 printed
4.
Step 8 of 20 · Exercise
Your turn: binary search
Write bsearch(xs, target): the index of target in the sorted list xs, or -1, by halving as in the trace. The
tests must pass, so the program prints:
all tests passed
Start with lo at the first index and hi at the last, len(xs) - 1. Loop while lo <= hi.
In the loop: mid = (lo + hi) // 2, then if, elif, else on xs[mid]. Return -1 after the loop.
elif xs[mid] < target:
lo = mid + 1
Step 9 of 20 · Quiz
How many rounds?
Each round of binary search halves what is left: 8 items need at most 4 rounds (8, 4, 2, 1). A sorted list has 1000 numbers. At most how many rounds does a search need?
Step 10 of 20 · Demo
Swap two items in one line
Python works out the right side first, as a tuple. Then it gives the tuple's items to the two places named before
the =, as lesson 11's a, b = b, a did. Run it.
Step 11 of 20 · Concept
Selection sort: smallest to the front
Selection sort makes one pass per place, from the front:
- Pass
ilooks at the items fromito the end and finds the index of the smallest. - It swaps that item with the one at
i.
After pass i, the items up to i are sorted and never move again. The last item is then already in place.
Step 12 of 20 · Quiz
After the first pass
Selection sort makes its first pass over this list. What is the list after it?
nums = [5, 3, 8, 1]
Step 13 of 20 · Exercise
Your turn: selection sort
Write selection_sort(xs): it sorts xs in place, smallest first, pass by pass. Do not call sorted or sort.
The program must print:
[1, 3, 5, 8]
all tests passed
A loop inside a loop (lesson 11). The outer one picks the place i; the inner one finds the smallest from i on.
Before the inner loop, smallest = i. Inside it, smallest = j when xs[j] is less than xs[smallest]. After it, swap.
xs[i], xs[smallest] = xs[smallest], xs[i]
Step 14 of 20 · Demo
What real code uses
Real code calls Python's own tools, tested and fast: sorted and sort (lesson 13), and Counter.
Counter(words) counts each item; most_common(2) gives the top two as (item, count) pairs. A text counts its
characters. Run it.
Step 15 of 20 · Try it
Try it: palindromes
A palindrome reads the same backwards. Run it: the second test fails, on a capital and the spaces.
Make a plain copy of text first, in small letters and without spaces, and compare that. The program must then
print:
all tests passed
Two text methods of lesson 9 make the plain copy: lower(), then replace(" ", ""). Compare that copy with
itself backwards.
Step 16 of 20 · Try it
Try it: reverse the words
reverse_words(text) cuts the text into words, then joins them in the same order. Add one slice to reverse
them. The program must then print:
sat cat the
all tests passed
[::-1] reverses a list as it reverses text (lesson 9). Put it on the list text.split() gives.
Step 17 of 20 · Try it
Try it: the top three letters
Run it: the third most common character is the space. Count text without its spaces, with replace, so the
program prints the top three letters:
p 8
e 7
r 3
text.replace(" ", "") is the text without its spaces. Give that to Counter.
Step 18 of 20 · Check yourself
Check yourself: second largest, tested
Write second_largest(xs): the second item of xs if it were sorted from the largest. xs has 2 items or more.
Do not sort: go through the list once.
The program must print:
6
all tests passed
Keep two names, the largest so far and the second, and decide for each item which of them it changes.
Step 19 of 20 · Challenge · optional
Challenge: merge two sorted lists
Optional.
Write merge(a, b): one sorted list of the items of the sorted lists a and b, without sorted. Walk both lists
at once with two indices. The program must print:
[1, 2, 3, 4, 9, 10, 12]
all tests passed
i walks a, j walks b. While both have items left, append the smaller of a[i] and b[j] and move on.
When one list is used up, the rest of the other is already sorted. result.extend(xs) appends every item of xs.
result.extend(a[i:])
result.extend(b[j:])
Step 20 of 20 · Recap
Recap
- Linear search looks at each item;
returninside the loop stops at the first match. - Binary search halves a sorted list: 10 rounds at most for 1000 items.
assertstops with anAssertionErrorwhen its condition isFalse; a test is a function of asserts.xs[i], xs[j] = xs[j], xs[i]swaps two items; selection sort swaps the smallest forward.- Real code calls
sorted,sortandCounter(...).most_common(n).
Next: lesson 22 builds a whole program of your own.
Review
2 questions from this lesson, in a new order each time. Answer from memory: 2 of 2 right on the first try passes. On a day after you finish the lesson, a pass earns 15 XP.
The review needs JavaScript.
def find(xs, target):
for i, x in enumerate(xs):
print("look at", x)
if x == target:
return i
return -1
nums = [7, 3, 9, 4, 9]
print(find(nums, 9))
print(find(nums, 5))
def find(names, name):
"""The index of the first item equal to name,
capitals ignored; -1 when there is none."""
for i, n in enumerate(names):
if n == name:
return i
return -1
names = ["Ada", "Alan", "Grace", "Alan"]
print(find(names, "alan"))
print(find(names, "GRACE"))
print(find(names, "Linus"))
def find(xs, target):
for i, x in enumerate(xs):
if x == target:
return i
return -1
def test_find():
assert find([7, 3, 9, 4, 9], 9) == 2
assert find([7, 3, 9], 5) == -1
assert find([], 1) == -1
test_find()
print("all tests passed")
def count_vowels(word):
"""How many of word's letters are vowels."""
count = 0
for ch in word:
if ch in "aeiou":
count += 1
return count
def test_count_vowels():
assert count_vowels("python") == 1
assert count_vowels("banana") == 3
assert count_vowels("Ada") == 2
test_count_vowels()
print("all tests passed")
def bsearch(xs, target):
"""The index of target in the sorted list xs,
or -1 when it is not there."""
return -1
def test_bsearch():
nums = [3, 8, 12, 15, 23, 31, 40, 47]
assert bsearch(nums, 23) == 4
assert bsearch(nums, 3) == 0
assert bsearch(nums, 47) == 7
assert bsearch(nums, 20) == -1
assert bsearch([], 5) == -1
test_bsearch()
print("all tests passed")
nums = [6, 4, 9, 2]
nums[0], nums[3] = nums[3], nums[0]
print(nums)
def selection_sort(xs):
"""Sort xs in place, smallest first."""
pass
def test_sort():
nums = [5, 3, 8, 1]
selection_sort(nums)
assert nums == [1, 3, 5, 8]
words = ["pear", "fig", "apple"]
selection_sort(words)
assert words == ["apple", "fig", "pear"]
nums = [5, 3, 8, 1]
selection_sort(nums)
print(nums)
test_sort()
print("all tests passed")
from collections import Counter
nums = [5, 3, 8, 1]
print(sorted(nums))
print(nums)
nums.sort()
print(nums)
words = "the cat and the dog and the end".split()
print(Counter(words).most_common(2))
print(Counter("banana").most_common(1))
def is_palindrome(text):
"""True when text reads the same backwards,
capitals and spaces ignored."""
return text == text[::-1]
def test_palindrome():
assert is_palindrome("level")
assert is_palindrome("Never odd or even")
assert not is_palindrome("python")
test_palindrome()
print("all tests passed")
def reverse_words(text):
"""The words of text in the opposite order."""
return " ".join(text.split())
def test_reverse_words():
assert reverse_words("one two three") == "three two one"
assert reverse_words("hello") == "hello"
print(reverse_words("the cat sat"))
test_reverse_words()
print("all tests passed")
from collections import Counter
text = "peter piper picked a peck of peppers"
letters = Counter(text)
for letter, n in letters.most_common(3):
print(letter, n)
def second_largest(xs):
"""The second largest item of xs (2 items or
more), without sorting."""
return xs[0]
def test_second_largest():
assert second_largest([3, 9, 4, 7]) == 7
assert second_largest([9, 3]) == 3
assert second_largest([5, 5, 3]) == 5
assert second_largest([1, 2, 3, 4]) == 3
print(second_largest([8, 2, 6]))
test_second_largest()
print("all tests passed")
def merge(a, b):
"""One sorted list of the items of the sorted
lists a and b."""
return a + b
def test_merge():
assert merge([1, 4, 9], [2, 3]) == [1, 2, 3, 4, 9]
assert merge([], [5]) == [5]
assert merge([2, 2], [1, 2]) == [1, 2, 2, 2]
print(merge([1, 4, 9], [2, 3, 10, 12]))
test_merge()
print("all tests passed")