The shape of the lesson
By the end of the lesson, learners can
- Linear search: In the lab, search for a value that is in the list and then for one that is not.
- Bubble sort: In the lab, step through a bubble sort.
- A smarter bubble sort: Two improvements cut the work: stop as soon as a whole pass makes no swaps, because the array must then be sorted, and make each pass one comparison shorter, because the end of the array is already in order.
- Linear search: WHILE not found AND not past the end; compare, then move on; report after the loop.
- Bubble sort: compare List[j] with List[j + 1]; swap with Temp if in the wrong order.
- Bounds: j stops one before the last element in use, so List[j + 1] stays in range.
- Improve: reset a Swapped flag every pass, stop when it stays FALSE, shorten each pass.
One picture every idea returns to
A linear search compares the target with each element in turn, from the first, and stops when it is found or the end of the array is reached. It works on unsorted data; in the worst case it makes n comparisons. A bubble sort compares each pair of adjacent elements and swaps them (using a temporary variable) if they are in the wrong order. After each pass the largest unsorted value has reached its final place. The improved version uses a flag to stop as soon as a pass makes no swaps and shortens each pass by one.
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, Look, then swap.. The two array algorithms the AS syllabus names. 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 | In the lab, search for a value that is in the list and then for one that is not. Project tab 1 of the lab (Linear search) and let a student drive it while the class predicts. Model the worked example Count the comparisons on the board, one line at a time. Your turn: Why does this linear search use a WHILE loop rather than a FOR loop from 1 to 8? | Whole class, then pairs |
| 13 to 21 min | Teach and check: Bubble sort | In the lab, step through a bubble sort. Project tab 2 of the lab (Bubble sort) and let a student drive it while the class predicts. Model the worked example One pass by hand on the board, one line at a time. Your turn: Continue the sort. What does the array hold after pass 2? | Pairs |
| 21 to 30 min | Teach and check: A smarter bubble sort | Two improvements cut the work: stop as soon as a whole pass makes no swaps, because the array must then be sorted, and make each pass one comparison shorter, because the end of the array is already in order. Model the worked example Trace the improved sort on the board, one line at a time. Your turn: The improved sort is run on 3, 5, 6, 8, 9, which is already sorted. How many comparisons does it make? | Frayer Model |
| 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, 24 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 A smarter bubble sort, 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.
Frayer Model
Pairs fill a four-box grid for the key term: definition, characteristics, examples and non-examples. The non-examples box is where the misconceptions surface, so give it the most time.
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 put OUTPUT "not found" inside the loop: it would be output for every element that does not match. | Decide only after the loop has finished, using the Found flag. |
| Writing the swap as Nums[j] ← Nums[j + 1] then Nums[j + 1] ← Nums[j] copies one value into both elements. | Always use a temporary variable. |
| Set Swapped ← FALSE at the start of every pass, inside the REPEAT. | Setting it once before the loop means a single swap in pass 1 keeps it TRUE for ever. |
Linear search and bubble sort: worksheet
6 questions, 24 marks. Written in the style of the papers; no past paper question is reproduced.
Describe how a linear search finds a value in a 1D array.
Using the linear search in this lesson, Names holds Pia, Leo, Sam, Ada, Tia, Jon, Kai, Uma. State the final value of Index, the output and the number of comparisons when SearchName is (a) Jon (b) Zac.
The improved bubble sort in this lesson is used on an array of 4 elements holding 7, 3, 9, 1 (with Top ← 4). Show the contents of the array after each pass and state how many passes are made.
IDs : ARRAY[1:100] OF STRING is a global array. Write pseudocode for a function FindID(SearchID : STRING) RETURNS INTEGER that uses a linear search and returns the index of SearchID, or −1 if it is not found.
Names : ARRAY[1:50] OF STRING holds 50 names. Write pseudocode for an efficient bubble sort that puts the names into alphabetical order and stops as soon as the names are sorted.
An array of 10 integers is already in ascending order. Compare the number of comparisons made by (a) a simple bubble sort with two FOR loops from 1 to 9 and (b) the improved bubble sort. Explain the difference.
Answer key and marking notes
- Start at the first element (lower bound).
- Compare each element with the search value in turn, moving to the next if it does not match.
- Stop when the value is found (output its index) or when the last element has been checked (output not found).
- (a) Index = 6; output
Jon found at position 6; 6 comparisons. - (b) Index = 9; output
Zac not found. - (b) 8 comparisons.
- After pass 1: 3, 7, 1, 9.
- After pass 2: 3, 1, 7, 9.
- After pass 3: 1, 3, 7, 9.
- Top becomes 1 after pass 3, so 3 passes are made.
- Function header and
ENDFUNCTION; local Index initialised to 1 and a flag (or a result variable) initialised. - Loop while Index <= 100 and the item is not found.
- Compare
IDs[Index] = SearchID; if equal set the flag / store the index. - Otherwise increment Index.
RETURN Indexif found, elseRETURN -1.
- Declare and initialise
Top ← 50(or a pass-length variable). - Outer
REPEAT...UNTIL Swapped = FALSE OR Top = 1(or a WHILE equivalent). Swapped ← FALSEat the start of each pass.- Inner
FOR j ← 1 TO Top - 1comparingNames[j] > Names[j + 1]. - Swap using a temporary STRING variable and set
Swapped ← TRUE. Top ← Top - 1after each pass.
- (a) 9 passes × 9 comparisons = 81.
- (b) 9 comparisons: one pass only.
- No swaps are made in the first pass, so the flag stays FALSE and the improved sort stops; the simple sort always completes every pass.
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.
Which statement about a linear search is correct?
- AIt works on unsorted data, but may have to compare the target with every element
- BIt only works if the array has first been sorted into order
- CIt always finds the target in a single comparison
- DIt halves the number of elements still to check after each comparison
Values holds 14, 8, 33, 33, 21, 5, 40, 2, 17, 9 in elements 1 to 10. A linear search for 33 uses WHILE Index <= 10 AND Found = FALSE, incrementing Index only when there is no match. What is the result?
- AFound at position 3 after 3 comparisons
- BFound at position 4 after 4 comparisons
- CFound at position 3 after 10 comparisons
- DFound at positions 3 and 4 after 10 comparisons
An array holds 9, 4, 7, 2, 8. What does it hold after the first pass of a bubble sort into ascending order?
- A4, 7, 2, 8, 9
- B2, 4, 7, 8, 9
- C4, 9, 7, 2, 8
- D4, 2, 7, 8, 9
A simple bubble sort uses two nested FOR loops, each running from 1 to n − 1, and makes one comparison per inner pass. How many comparisons does it make for an array of 8 elements?
- A49
- B64
- C56
- D28
The improved bubble sort below is run on an array of 6 elements holding 2, 1, 3, 4, 5, 6. How many comparisons does it make in total?
Top ← 6
REPEAT
Swapped ← FALSE
FOR j ← 1 TO Top - 1
IF Nums[j] > Nums[j + 1] THEN
Temp ← Nums[j]
Nums[j] ← Nums[j + 1]
Nums[j + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT j
Top ← Top - 1
UNTIL Swapped = FALSE OR Top = 1- A9
- B5
- C15
- D25
In the improved bubble sort above, a programmer moves Swapped ← FALSE to just before REPEAT, so it runs only once. What is the effect?
- AOnce any swap is made the flag stays TRUE, so the sort cannot stop early and runs until Top = 1
- BThe sort stops after the first pass, before the array has been fully sorted
- CThe loop never ends, because Swapped can no longer become FALSE
- DThe array is sorted into descending order instead of ascending order
Quiz key
Because it checks elements in order from the start, a linear search needs no sorting, but in the worst case (target last or missing) it makes n comparisons. Needing sorted data and halving the search area both describe a binary search, and one comparison is only the best case.
The comparisons are with 14, 8 and then 33 at index 3, which sets Found to TRUE, so the loop stops after 3 comparisons with Index = 3. Position 4 would be the last match, but the search stops at the first. A FOR loop would make 10 comparisons, and this search reports only one position.
9 > 4 swap (4, 9, 7, 2, 8); 9 > 7 swap (4, 7, 9, 2, 8); 9 > 2 swap (4, 7, 2, 9, 8); 9 > 8 swap (4, 7, 2, 8, 9). The largest value has reached the end. 2, 4, 7, 8, 9 is the fully sorted array, 4, 9, 7, 2, 8 stops after one comparison, and 4, 2, 7, 8, 9 is what the array holds after the second pass.
There are 7 passes of 7 comparisons each, so 7 × 7 = 49, whatever the data. 64 uses 8 for both loops, 56 uses 8 passes of 7, and 28 (7 + 6 + ... + 1) is what a version that shortens each pass would make.
Pass 1 (j = 1 to 5) makes 5 comparisons and one swap, giving 1, 2, 3, 4, 5, 6, so Swapped is TRUE and the loop continues. Pass 2 (j = 1 to 4) makes 4 comparisons and no swaps, so the sort stops: 5 + 4 = 9. 5 assumes it stops after the first pass, although that pass made a swap; 15 runs every shortened pass; 25 is the simple sort's 5 × 5.
After the first swap Swapped is TRUE and is never reset, so Swapped = FALSE can no longer end the loop; it carries on until Top = 1, losing the early stop but still sorting correctly. It does not stop after a pass that made swaps, the Top = 1 condition guarantees that the loop ends, and the comparison is unchanged, so the order is still ascending.
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.