The shape of the lesson
By the end of the lesson, learners can
- Linear search: Step through the search in the lab.
- Bubble sort: Watch the bubble sort in the lab.
- Pass by pass: Exam questions often ask for the list after each pass.
- Linear search: start at item 1; compare; move on; stop when found or at the end.
- Bubble sort: compare neighbours; swap if in the wrong order (using Temp).
- Pass: one run through the list; the largest remaining value reaches its place.
- Stop: when a whole pass makes no swaps.
One picture every idea returns to
A linear search checks each item of a list in turn, from the first, until the item is found or the end of the list is reached. A bubble sort compares each pair of adjacent items and swaps them if they are in the wrong order. One pass moves the largest remaining item to the end. Passes repeat until a whole pass makes no swaps, so the list is sorted.
Forty-five minutes, phase by phase
| Time | Phase | What happens in the room | Grouping |
|---|---|---|---|
| 0 to 5 min | Hook: predict | Open with the question in the title, Find it, then sort it.. Two standard methods appear again and again in exam algorithms. Put the figure on the board: it is the one picture every idea in the lesson returns to. | Whole class, then pairs |
| 5 to 13 min | Teach and check: Linear search | Step through the search in the lab. Project tab 1 of the lab (Linear search step by step) and let a student drive it while the class predicts. Model the worked example Search for Dev on the board, one line at a time. Your turn: How many comparisons are made if the user enters Gus, and what is output? | Whole class, then pairs |
| 13 to 21 min | Teach and check: Bubble sort | Watch the bubble sort in the lab. Project tab 2 of the lab (Bubble sort step by step) and let a student drive it while the class predicts. | Pairs |
| 21 to 30 min | Teach and check: Pass by pass | Exam questions often ask for the list after each pass. Project tab 2 of the lab (Standard methods in pseudocode) and let a student drive it while the class predicts. Your turn: Write the list 6, 2, 8, 4 after the first pass of a bubble sort into ascending order. | Connect-Extend-Challenge |
| 30 to 36 min | Check | The four Stage 1 questions from the student lesson, answered on mini whiteboards or by show of fingers. Re-teach the one most get wrong. | Individual, then whole class |
| 36 to 43 min | Plenary | The exam-style questions from Stage 2, one at a time: thirty seconds alone, then a random call. The feedback lines in the key give the examiner's wording. | Individual, random call |
| 43 to 45 min | Exit and homework | Set the worksheet below (6 questions, 18 marks). Learners self-assess against the objectives before they leave. | Individual |
Protect the parts that carry the learning
The sequence carries about fifty minutes of material, so the lab is driven by one student while the class predicts rather than explored freely. Times are a guide.
Protected: the check at 30 minutes. It is the only individual read on whether the key idea landed, and it is not cut.
Cut first if the build overruns: the last check in Pass by pass, never the check or the plenary.
In a 60 minute block: run worksheet questions 1 to 3 in class as a Rally Coach set and model both the hardest worked example and its check live.
Connect-Extend-Challenge
After the new idea, each student writes three lines: how it connects to what they knew, how it extends their thinking, and what still challenges them. Pairs compare, then the challenges become the plenary.
The full structure, with its variations and the other twelve, is on the cooperative-learning page.
What to head off, and how
| Trap learners fall into | Teaching move that pre-empts it |
|---|---|
| Do not stop the search with only one condition. | The loop needs both: stop when the item is found or when the end of the list is reached, otherwise a missing item makes Index run past the end of the array. |
| Swapping with Values[Index] ← Values[Index + 1] followed by Values[Index + 1] ← Values[Index] does not swap: both end up as the same value. | Always use a temporary variable. |
| The list can be sorted before the algorithm knows it. | After pass 3 it is in order, but one more pass is needed to make no swaps and confirm it. |
Standard methods: linear search and bubble sort: worksheet
6 questions, 18 marks. Written in the style of the papers; no past paper question is reproduced.
Describe how a linear search finds an item in an array.
The array Scores holds 12, 45, 7, 45, 30. A linear search for 45 stops when it finds the first match. State how many comparisons are made and the position output. Then state how many comparisons are made for a search for 8.
Show the list 8, 6, 9, 2 after each pass of a bubble sort into ascending order.
The array Prices[1:10] holds real numbers. Write pseudocode for a bubble sort that puts Prices into ascending order, stopping when a pass makes no swaps.
Explain why a bubble sort needs a temporary variable when it swaps two values.
A bubble sort is run on a list that is already in ascending order. Explain how many passes a sort with a swap flag makes, and why.
Answer key and marking notes
- Start at the first element of the array.
- Compare each element with the item searched for, moving to the next element each time.
- Stop when the item is found, or when the end of the array is reached (item not found).
- Searching for 45: 2 comparisons (12, then 45).
- Position 2 is output.
- Searching for 8: 5 comparisons (every element checked; not found).
- After pass 1: 6, 8, 2, 9.
- After pass 2: 6, 2, 8, 9.
- After pass 3: 2, 6, 8, 9 (now in ascending order).
- Outer REPEAT ... UNTIL loop (or WHILE) that ends when no swap is made in a pass.
- Set a flag, e.g. Swap ← FALSE, at the start of each pass.
- Inner FOR loop from 1 TO 9 (one less than the number of items) comparing Prices[Index] > Prices[Index + 1].
- Swap using a temporary variable: Temp ← Prices[Index]; Prices[Index] ← Prices[Index + 1]; Prices[Index + 1] ← Temp.
- Set Swap ← TRUE when a swap is made.
- When the first value is overwritten by the second, the first value is lost.
- Temp stores the first value so it can then be copied into the second position.
- Only one pass is made.
- No pair is out of order, so no swaps are made in that pass, the flag stays FALSE and the sort stops.
6 multiple-choice questions on this lesson
From the topic question bank. Assign them in the app for a marked score in your gradebook, or run the topic as a class game.
The array Codes holds 15, 8, 23, 8, 42, 16 in that order. A linear search starts at the first element and stops as soon as it finds 42. How many comparisons are made?
- A5
- B6
- C4
- D1
What is the list 9, 4, 7, 1, 6 after the first pass of a bubble sort into ascending order?
- A4, 7, 1, 6, 9
- B1, 4, 6, 7, 9
- C4, 9, 7, 1, 6
- D4, 1, 6, 7, 9
A bubble sort uses a Boolean variable Swap, set to FALSE at the start of each pass. Why?
- AIf a whole pass makes no swaps the list is sorted, so the sort can stop
- BIt stores one value while two values are being exchanged
- CIt counts the number of passes made through the list
- DIt records the position of the largest value in the list
An array holds 12 different product codes. A linear search is made for a code that is not in the array. How many comparisons are made?
- A12
- B11
- C6
- D13
The list 5, 1, 2, 3, 4 is sorted into ascending order with this bubble sort (as in the lesson). How many comparisons are made in total?
Last ← 5
REPEAT
Swap ← FALSE
FOR Index ← 1 TO Last - 1
IF Values[Index] > Values[Index + 1]
THEN
Temp ← Values[Index]
Values[Index] ← Values[Index + 1]
Values[Index + 1] ← Temp
Swap ← TRUE
ENDIF
NEXT Index
Last ← Last - 1
UNTIL Swap = FALSE OR Last = 1- A7
- B4
- C10
- D16
Names[1:6] holds Ali, Bea, Chen, Dev, Eva, Finn. A student changes the linear search so that Index always increases. What is output when the user enters Chen?
Found ← FALSE
Index ← 1
WHILE Found = FALSE AND Index <= 6 DO
IF Names[Index] = SearchName
THEN
Found ← TRUE
ENDIF
Index ← Index + 1
ENDWHILE
IF Found = TRUE
THEN
OUTPUT SearchName, " found at position ", Index
ELSE
OUTPUT SearchName, " not found"
ENDIF- AChen found at position 4
- BChen found at position 3
- CChen not found
- DChen found at position 7
Quiz key
The search compares 15, 8, 23, 8 and then 42, which matches: 5 comparisons. It stops there, so 16 is never checked and the answer is not 6. Counting only the four elements before the match forgets the comparison that finds it. A linear search cannot jump straight to the item, so 1 is impossible here.
9 > 4 swap (4, 9, 7, 1, 6); 9 > 7 swap (4, 7, 9, 1, 6); 9 > 1 swap (4, 7, 1, 9, 6); 9 > 6 swap (4, 7, 1, 6, 9). The 9 bubbles to the end. 1, 4, 6, 7, 9 is the fully sorted list, which takes more passes. 4, 9, 7, 1, 6 is after only one comparison. 4, 1, 6, 7, 9 is the list after the second pass.
Swap is set to TRUE whenever a pair is exchanged. If it is still FALSE after a pass, nothing was out of order, so the algorithm can stop early. Holding a value during an exchange is the job of Temp. A Boolean can only be TRUE or FALSE, so it cannot count passes or store a position.
The item is not found, so every one of the 12 elements is compared before the end of the array is reached. Stopping at 11 would leave the last element unchecked. 6 would be half the list, as if the search could skip items. There is no 13th element to compare.
Pass 1 makes 4 comparisons and moves 5 to the end, giving 1, 2, 3, 4, 5, but Swap is TRUE so another pass runs. Pass 2 makes 3 comparisons (Last is now 4) with no swaps, so the loop stops: 4 + 3 = 7. Answering 4 forgets the confirming pass. 10 is 4 + 3 + 2 + 1, every pass without the early stop. 16 assumes 4 passes of 4 comparisons, ignoring both the flag and Last.
At Index 3 the names match and Found becomes TRUE, but Index is still increased to 4 before the loop condition is tested again, so the output gives position 4 (one too many). Position 3 is what the correct algorithm outputs. Found is TRUE, so "not found" is not output. The loop stops as soon as Found is TRUE, so Index never reaches 7.
What to project
The student lesson embeds these tabs. Open them full screen on the projector; every slider has a drag handle on the stage.
Slides for this lesson
A projectable deck for every pack is on the way. Until then, present the student lesson full screen: its sections, figure and lab tabs follow the same order as the plan above.