DSE ICT | Sorting and Searching Algorithms: Tutor Lesson Plan

2026-11-05

Tutor lesson-prep guides · Secondary ICT

Students can chant that binary search is faster, yet cannot say how many comparisons 1024 items need. This lesson makes them count it once, so the slogan becomes a number.

Objectives — Students can: (1) distinguish bubble, insertion and selection sort; (2) write one pass of a sort in a trace table; (3) compute search costs: 1024 comparisons linear versus 10 binary on 1024 items.

01 Prerequisites (3-minute check)

If any of these fails, fix it before the lesson starts.

Skill	Quick check	Pass mark
Arrays	Indexing starts at zero	Last index is length minus one
Loops	for versus while	while suits searching
Comparisons	Greater, less and equal	Sorting uses only pairwise comparison

02 Lesson flow (60 minutes)

Time	Stage	Tutor does	Student does
0-8 min	Diagnosis	Order four numbers once	Say the steps aloud
8-22 min	Three sorts	Bubble, insertion, selection	Write one pass each
22-36 min	Trace table	Comparisons and swaps per pass	Fill the table
36-48 min	Two searches	Linear and binary	Compute comparison counts
48-56 min	Question drill	Spot the error, count the steps	Answer in steps
56-60 min	Exit check	Three quick items	Spoken answers

03 Teaching script (read it out)

Scene 1: Act 1: Three sorts differ only in when they swap

Bubble sort compares neighbours and swaps when out of order, pushing the maximum to the end each pass. Insertion sort lifts each item into the sorted prefix. Selection sort finds the minimum each pass and places it at the front. On 8 items all three need 28 comparisons in the worst case.
Students do: run one pass of each on the same eight numbers.
Common slip: assuming selection sort compares less; in the worst case it does not.

Tutor move: ask only which pair was compared this pass; no full code.

Scene 2: Act 2: Linear search is the one that needs no sorting

Linear search checks every item, so the worst case is 1024 inspections on 1024 items, and about 512 on average. Its advantage is that unordered, frequently updated data needs no preparation.
Students do: name the situation where linear search is the right choice.
Common slip: quoting the average as the worst case and answering 512.

Tutor move: have them find the last item in a 1024-cell grid and count their own looks.

Scene 3: Act 3: Binary search halves the problem

Binary search requires sorted data. Each comparison halves the range: 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, so the worst case is 10 comparisons, because 2 to the power 10 is 1024. That is roughly 102 times cheaper than linear search.
Students do: count the halvings by hand and check the formula.
Argument: the price of that speed is the sorting step, which must be paid first.

Tutor move: refuse binary search on unsorted data until they sort it, then ask what goes wrong.

04 Question types and worked steps

Type	Example	Steps
Write one pass	Fix the direction, compare pairs, swap, record the pass	One pass only
Trace table	Record pair, swap, array state per line	One action per cell
Count comparisons	Decide linear or binary, apply the rule, substitute n	Binary is ceil of log2 n
Spot the error	Check sortedness, midpoint, boundaries	One fault per item

Sanity check (teach this): On 1024 sorted items binary search needs 10 comparisons, while linear search needs 1024; answering 11 is wrong because the final comparison already finds the item. On 8 items a bubble sort needs 28 comparisons in the worst case, and all three simple sorts share that bound. Binary search on unsorted data is always wrong.

05 Independent practice (3 questions)

Question	Answer	What to watch
Binary search worst case, 1024 items	10	log2 of 1024
Linear search worst case, 1024 items	1024	One look per item
Worst case for a simple sort, 8 items	28	8 times 7 over 2

06 Common mistakes and what to say

Mistake	Student writes	Say this
Answering 11 comparisons	Counting a failed final test	“Did the last comparison find it?”
Binary search on unsorted data	Halving a random array	“What must be true before you halve?”
Average confused with worst case	Answering 512 for linear search	“Which item is the worst?”
Assuming selection sort is cheaper	Answering 7 comparisons	“How many did you compare per pass?”

07 Homework (paper, section and question numbers)

Sorting trace set (in-house) — Questions 1-4: one pass of each sort
Search counting set (in-house) — Questions 5-7: linear and binary counts

08 Exit check (last 5 minutes)

Question	Answer	Decision
Binary search worst case, 1024 items	10	Wrong: reteach halving
Precondition for binary search	Sorted data	Wrong: reteach the precondition
Worst case for a simple sort, 8 items	28	Wrong: reteach n(n-1)/2

09 Tutor FAQ

Why round the halving up

Halving until one item remains still needs that final comparison, so round up.

Which sort do real programs use

A hybrid of quicksort and insertion sort, but exams test the three simple sorts.

When is linear search better

Small, unsorted and frequently updated data, where sorting costs more than it saves.

Find a tutor — free Tutor Registration →

A TutorZone lesson-prep guide. Written by the TutorZone team; questions and lesson flow are original and are not taken from any school or publisher material.