Lesson 6: Functions and recursion
Build the sorting race in Python, and learn on the way:
- functions, and passing a function as a value
- recursion: a function that calls itself on smaller parts
- a counter kept in a dictionary
- assert to check a result
- how work grows: n² against n·log n
Watch it first
Plays from YouTube after a click.
The script
Open in Colab: this lesson as a notebook"""Sorting race: four algorithms on the same shuffled list, counting their comparisons.
Run: python sorting-race.py (needs: pip install numpy matplotlib)
"""
import math
import numpy as np
import matplotlib.pyplot as plt
plt.style.use("dark_background")
n = 100
data = list(np.random.default_rng().permutation(n))
count = {"comparisons": 0}
def less(a, b): # every algorithm compares only through this, so we can count
count["comparisons"] += 1
return a < b
def bubble(xs):
xs = xs[:]
for end in range(len(xs) - 1, 0, -1):
for i in range(end):
if less(xs[i + 1], xs[i]):
xs[i], xs[i + 1] = xs[i + 1], xs[i]
return xs
def insertion(xs):
xs = xs[:]
for i in range(1, len(xs)):
j = i
while j > 0 and less(xs[j], xs[j - 1]):
xs[j], xs[j - 1] = xs[j - 1], xs[j]
j -= 1
return xs
def merge(xs):
if len(xs) < 2:
return xs
left, right = merge(xs[: len(xs) // 2]), merge(xs[len(xs) // 2 :])
out = []
while left and right:
out.append(left.pop(0) if not less(right[0], left[0]) else right.pop(0))
return out + left + right
def quick(xs):
if len(xs) < 2:
return xs
pivot, rest = xs[0], xs[1:]
smaller = [x for x in rest if less(x, pivot)]
return quick(smaller) + [pivot] + quick([x for x in rest if x not in smaller])
results = {}
for name, sort in [("bubble", bubble), ("insertion", insertion), ("merge", merge), ("quick", quick)]:
count["comparisons"] = 0
assert sort(data) == sorted(data)
results[name] = count["comparisons"]
print(results, "| at least log2(n!) =", math.ceil(math.log2(math.factorial(n))))
plt.figure(figsize=(7, 4))
plt.bar(list(results), list(results.values()), color=["#f0abfc", "#c4b5fd", "#5eead4", "#5eead4"])
plt.axhline(math.log2(math.factorial(n)), color="white", linestyle="--", label="log2(n!): no comparison sort does better")
plt.ylabel(f"comparisons for n = {n}")
plt.legend()
plt.show()
# Try: n = 1000 (bubble sort needs about n*n/2, merge sort about n*log2(n))
No Python on this computer? The notebook runs the same script, the exercises and the answers in your browser, on Google Colab.
Line by line
def less(a, b):Every algorithm compares through this one function, so the comparisons can be counted in one place.
count["comparisons"] += 1A dictionary holds the count, so the function can change it without the global keyword.
def merge(xs):Merge sort: sort each half, then merge the two sorted halves by always taking the smaller front item.
left, right = merge(xs[: len(xs) // 2]), merge(xs[len(xs) // 2 :])Recursion: merge calls itself on each half, until a part has fewer than two items.
assert sort(data) == sorted(data)assert stops the script if a sort gets the order wrong: a test built into the program.
math.ceil(math.log2(math.factorial(n)))The lower bound: log₂ of the number of possible orders, n!, rounded up.
Try it yourself
For n = 100, which sort needs the fewest comparisons, and how close is it to the bound?
Hint
Run the script; it prints the counts and the bound.
Answer
Merge sort, about 540 against a bound of 525. Bubble sort needs exactly 4,950, that is 100 · 99 ÷ 2.
Why does this bubble sort always need n·(n − 1) ÷ 2 comparisons?
Hint
Look at its two loops.
Answer
This version always runs both loops to the end: (n − 1) + (n − 2) + … + 1 = n·(n − 1) ÷ 2 comparisons, whatever the order.
Give quick sort a list that is already sorted. What happens to its count?
Hint
data = list(range(n)).
Answer
It jumps to 4,950, as bad as bubble sort: with the first item as pivot, every split leaves one side empty.
Quiz
Flashcards
Read the front, say the back to yourself, then open the card.
Recursion
A function that solves a problem by calling itself on smaller parts of it.
assert condition
Stops the program with an error if the condition is False.
log₂(n!)
The fewest yes-or-no comparisons that can tell n! orders apart: the limit for any comparison sort.
n² against n·log n
For 1,000 items: about 500,000 against about 10,000 steps.
Passing a function
for name, sort in [("merge", merge), …]: functions are values, like numbers.