know.

CookbookLabs and workshopsNo. 28

An intro programming courseunits, worked examples and sorting you can watch

Recipe No. 28 · Labs and workshops

For: A teacher running a first programming course in Python

You get: A Python course: tested examples, Bug sections and sorting to watch

Time: An evening to draft, two to run it all

See it in know.sh

Try it. Four sorting algorithms on the same sixteen bars. Pick one, then press Step or Play and watch every comparison and swap.

A unit as a document: its aims, then a table element comparing its algorithms, with Python’s own sort marked as the pick.

Intro to programmingNo. 5

Unit 5 — Searching and sorting

14 sections, 4,020 words, about 17 minutes, filed 30 August, revised 22 September, 5 highlights.

Two weeks. By the end, students can trace linear and binary search by hand, write insertion sort from memory, and say why merge sort beats it on a long list and loses to it on a short, nearly sorted one. Every example runs on Python 3.12; the exercise files are in the class repository, unit-05.

Sections 3 to 6 each hold one algorithm, with its code, a trace and a Bug or two; the visualiser is in section 3.

Sections

  1. 1Linear searchInsight
  2. 2Binary search, and why the list must be sortedInsight, key
  3. 3Insertion sortInsight, key, 2 code blocksTake the next item and walk it left through the sorted part until the item before it is not larger.
  4. 4Selection and bubble sortInsight
  5. 5Merge sortInsight, key
  6. 6My list came back as NoneBug, keyitems.sort() sorts in place and returns None; sorted(items) returns a new list.

and eight more sections

A concept as a section: the idea, the code, a trace checked by running it, and a proposed note from Claude catching an off-by-one in the prose.

Intro to programmingUnit 5 — Searching and sorting

3of 14

Insertion sort

Insight, key section, 2 code blocks, 1 highlight, 1 note, 310 words

The idea. Take the next item and walk it left through the sorted part, swapping as you go, until the item before it is not larger. It is how most people sort a hand of cards.

def insertion_sort(items):
    """Sort a list in place, smallest first."""
    for i in range(1, len(items)):
        j = i
        while j > 0 and items[j - 1] > items[j]:
            items[j - 1], items[j] = items[j], items[j - 1]
            j -= 1

Worked example. insertion_sort([5, 2, 4, 1]), one line per pass:

start          [5, 2, 4, 1]
i = 1, take 2  [2, 5, 4, 1]   1 comparison, 1 swap
i = 2, take 4  [2, 4, 5, 1]   2 comparisons, 1 swap
i = 3, take 1  [1, 2, 4, 5]   3 comparisons, 3 swaps

Why it matters. Six comparisons and five swaps, and exactly one swap for every pair that started out of order: (5, 2), (5, 4), (5, 1), (2, 1) and (4, 1). On a list already in order it makes one comparison per item and no swaps at all, which is why Python’s own sort uses a form of insertion sort on short runs.

Watch it. Open the visualiser under this section, choose Insertion, and press Step: the swaps counter always ends on the number of pairs the starting order had out of order.

Ran on Python 3.12, 20 September.

How it works

Put your intro course in one place, mistakes included. Each unit is a document: a section per concept with a worked example and a trace, a section per exercise, and every mistake your classes make filed as a Bug. Beside the sorting unit sits a visualiser that counts every comparison and swap as the bars move.

  1. Give your assistant one unit at a time

    Hand over the slides and exercise files for one unit. Ask for a section per concept with a worked example and a trace, and each model answer in its own section.

  2. Run every example yourself

    Copy each code block into your own editor and run it on the input the section gives. Where the output and the trace disagree, fix the section.

  3. Ask for a sorting visualiser, and test it

    Ask for a widget element: sixteen bars, four algorithms, Step and Play. Selection sort on sixteen bars must make 120 comparisons every time, whatever the order.

  4. File the mistakes as Bugs

    After each lesson, ask your assistant to add each mistake as a Bug section titled with what the student saw: My list came back as None. Share each unit without the model answers.

Try this prompt

Your assistant, connected to know.sh (Claude, ChatGPT or a local model):

Write a widget element for section 3 of Unit 5 in my know.sh library: a sorting visualiser with sixteen bars from a fixed seed, and bubble, insertion, selection and merge sort on the same bars. Add Step, Play, Reset and a speed slider, and running counts of comparisons and swaps. Use only the page’s colours, and tell me the counts to expect so I can check it.

Your assistant, connected to know.sh (Claude, ChatGPT or a local model):

Using know.sh, make a shelf called Intro to programming and a document called “Unit 5 — Searching and sorting” from my slides and exercise files. One Insight section per concept, with the idea in two sentences, a worked example in a Python 3.12 code block and a line-by-line trace; one Question section per exercise; each model answer in its own Evidence section.

Made with

ShelfDocumentSectionYour AI assistantElementsPublic link

See also