Study Guide Instructor view
Linear Search and Bubble Sort
Teaching notes for Lesson 5.11, with controls for presenting it.
Keep this page on your own screen. Share only the lesson window. The lesson window holds no teaching notes, so sharing it cannot show them.
Presenting
- Open the lesson in its own window and share that window, not this one.
- Use Next and Previous here, or the lesson’s own, to move through the lesson. Next reveals one thing at a time: the next idea, or the answer to the question on screen, then the next step. Previous takes the last reveal back. The line below says what is on screen and what Next will show.
- Reveal hints and answers when the class is ready, and reset a demonstration before using it again.
The controls need JavaScript and a browser that supports BroadcastChannel. Without them, open the lesson in presentation mode and use its own controls.
The two windows talk to each other only inside this browser, on this device. Nothing is sent to a server, and no account is needed. A second device (a phone or another tablet) cannot follow the lesson window yet.
Now on the lesson window
- On screen
- Next teaching point
Guidance for this point
Lesson plan
- Level
- Intermediate
- Time
- About 90 minutes; the steps below add up to 90
Pupils start from a clipboard of six unordered names and invent the linear search before it is named, then physically act out one pass of a bubble sort with five pupils holding cards before they meet StepThrough and the code. The lesson then writes the bubble sort (why the inner loop stops at N - 1, why a swap needs Temp), adds a flag to stop early, and ends with fault-finding and a program of their own. Acting out and hand-tracing on small lists is the main teaching move: nearly every wrong answer can be settled by doing the pass with real cards.
Objectives
- Describe and write a linear search of an array, and explain why it checks every item when the item is not there
- Trace a linear search to say where an item was found, or that it was not found
- Describe how a bubble sort works, and say what each pass achieves
- Trace a bubble sort pass by pass, showing the array after each pass
- Write a bubble sort in pseudocode, explaining the swap, the bounds of the inner loop and the early-exit flag
- Spot and correct mistakes in a search or a sort
Before the lesson
- Five cards or sheets of paper numbered 5, 1, 4, 2 and 8 and five volunteers, or five coins on a desk, for the walk along the row in step 3.
- Mini whiteboards, one per pupil, for predictions and for writing the list after each pass.
- Write the Names array (Zoe, Raj, Mei, Tom, Ana, Leo) and the Numbers array (5 1 4 2 8) on the board as rows of boxes numbered from 1.
- Copy the linear search, bubble sort and flag version onto the board or slides so that you can trace them with the pen.
- A spare card for the temporary variable in the swap demonstration.
Steps
Introduction Opening
On the lesson window now
On screen: the lesson’s title, module and number; Next adds its objectives and key terms, as the lesson page lists them; Next again begins the first step.
Objectives on screen
- Describe and write a linear search of an array, and explain why it checks every item when the item is not there
- Trace a linear search to say where an item was found, or that it was not found
- Describe how a bubble sort works, and say what each pass achieves
- Trace a bubble sort pass by pass, showing the array after each pass
- Write a bubble sort in pseudocode, explaining the swap, the bounds of the inner loop and the early-exit flag
- Spot and correct mistakes in a search or a sort
Purpose: Pupils start from a clipboard of six unordered names and invent the linear search before it is named, then physically act out one pass of a bubble sort with five pupils holding cards before they meet StepThrough and the code. The lesson then writes the bubble sort (why the inner loop stops at N - 1, why a swap needs Temp), adds a flag to stop early, and ends with fault-finding and a program of their own. Acting out and hand-tracing on small lists is the main teaching move: nearly every wrong answer can be settled by doing the pass with real cards.
1. Is this name on the list? Think 6 min
On the lesson window now
Purpose: Pupils invent the linear search for themselves and say how many names they might need to read, before the algorithm is named.
Ask
- How would you find out whether Eve is in the club, step by step?
- What is the most names you might have to read before you can be certain?
Responses to expect
- Read from the top, comparing each name, stop on a match
- All six, because Eve might be missing or last
Misconceptions to challenge
- A learner may believe: “You can jump to the middle, as with a dictionary.” Respond: That works only if the names are in alphabetical order; these are in no order.
- A learner may believe: “You can tell Eve is missing after reading half the names.” Respond: Eve could be among the unread names; you are only sure once all are read.
Checking understanding: Pupils write the steps on a mini whiteboard; look for compare each name in turn and stop when found.
Depending on the answers
- If pupils say ask someone or look it up: ask them to imagine a clipboard that cannot be searched except by reading it, and to describe only their own steps.
English as an additional language
- Check clipboard, club and in no order; show a list of six names on a card.
Discussion pause: Thirty seconds of silent thinking, then pairs write the steps as a numbered list.
In the lesson window
- Think it through: Describe how you would find out, step by step. How many names might you have to read, at most, before you could say for certain whether Eve is in the club?
2. Looking at each item in turn Discover 14 min
On the lesson window now
Purpose: Pupils read the search algorithm, trace it for Tom, and say how many checks a missing name needs in a list of 1000; they also separate a search from a sort.
Ask
- Why does the loop condition have both Found = FALSE and Position <= 6?
- How many names are compared when the target is Tom?
- A club has 1000 names in no order: how many are compared for a name that is not there?
Responses to expect
- It stops when found or when the list runs out
- Four
- 1000, because absence can only be shown by checking all
Misconceptions to challenge
- A learner may believe: “The search needs the list to be in order.” Respond: A linear search works on any list; order makes no difference to it.
- A learner may believe: “On average the search stops halfway, so 500 are checked for a missing name.” Respond: That might happen when the name is there. If it is missing, it can never stop early.
- A learner may believe: “The search stops after the first comparison.” Respond: It stops early only on a match; Zoe is not Tom.
- A learner may believe: “A search and a sort do the same job.” Respond: A search finds an item and leaves the list alone; a sort rearranges it.
On the board or with the pen
- Draw the six boxes and write Position under the box being checked; write Found beside the array and update it as the trace goes. Circle the first match.
What learners should notice
- Position does not change after Found becomes TRUE, so it still says where Tom is.
Checking understanding: The worst-case check: the 500 and 1 options are the average and best-case slips.
Depending on the answers
- If pupils choose 500: ask what a search cannot know about a name that is missing until it has looked at the last name.
- If pupils are secure: ask the best case and worst case for the six-name list and say which names give each.
Support
- Give the trace table with the first row filled in and ask pupils to say each comparison aloud.
Stretch
- Why would the loop go wrong if the condition were Found = FALSE OR Position <= 6?
English as an additional language
- Check target, flag, found; use a looking-for-a-lost-sock example.
In the lesson window
- Check your understanding: A club has 1000 names in no order. A linear search looks for a name that is not in the list. How many names does it compare with the target?
3. Putting a list in order Predict 14 min
On the lesson window now
Purpose: Pupils act out one walk along a row of five pupils with cards, compare neighbours and swap, then watch it step by step, and do the second pass on paper.
Ask
- After one walk along the row, where does the 8 end up, and where does the 5 end up?
- What is the list after pass 2, and how many swaps were made?
Responses to expect
- 8 stays at the right and 5 ends up in the fourth place
- 1 2 4 5 8 with one swap
Misconceptions to challenge
- A learner may believe: “One pass puts the list in order.” Respond: Look at the list after pass 1: 1 4 2 5 8 is not in order. Only the largest value is in place.
- A learner may believe: “The 5 and the 8 are compared and swapped.” Respond: 5 is not greater than 8, so no swap; the 8 stays.
- A learner may believe: “Pupils can compare any two numbers.” Respond: Only neighbours are compared in a bubble sort.
- A learner may believe: “The program knows the list is in order after pass 2.” Respond: It does not yet; it only finds out when a pass makes no swaps.
On the board or with the pen
- Write 5 1 4 2 8 and write the list under it after each comparison, circling the pair compared; do the same for pass 2 on 1 4 2 5 8.
Follow-up questions
- Why does the 8 not need to be compared again in the next pass?
Checking understanding: Ask five pupils to act it out while the others write the list after each comparison; the 'after pass 2' answer shows who can transfer the process to a new row.
Depending on the answers
- If pupils swap 5 and 8: ask which number is bigger and what the rule says for a left number that is smaller.
- If pupils find the second pass easy: ask them to predict pass 3 without doing it and say how they know.
Support
- Give pupils number cards and let them physically swap neighbours.
Stretch
- After pass 1, how many values are certainly in their final place? After pass 2?
English as an additional language
- Check neighbour, swap and pass; mime swapping two cards.
In the lesson window
- Think it through: After one walk along the row, comparing each pair of neighbours and swapping where the left number is bigger, where does the 8 end up? And where does the 5 end up?
- Think it through: Without looking ahead, do a second pass on 1 4 2 5 8, by hand, on paper, comparing each neighbouring pair. What is the list after pass 2, and how many swaps were made?
4. Writing the bubble sort Explain 14 min
On the lesson window now
Purpose: Pupils see how one pass is written as a loop over pairs, why the inner loop stops at 4, why a swap needs Temp, and fill in the array after each pass.
Ask
- Why does the inner loop run Index from 1 to 4 for five elements?
- What is the array after each pass of the sort?
- Why is a temporary variable needed in the swap?
Responses to expect
- Index + 1 would be Numbers[6], outside the bounds
- 1 4 2 5 8, then 1 2 4 5 8, then unchanged
- Otherwise the left value is overwritten and lost
Misconceptions to challenge
- A learner may believe: “The loop should go to 5 because there are 5 elements.” Respond: Five elements make four neighbouring pairs; at Index = 5 the second element would not exist.
- A learner may believe: “One pass sorts the array.” Respond: One pass only moves the largest remaining value to its end.
- A learner may believe: “Passes 3 and 4 do something useful.” Respond: They make no swaps; they are wasted work, which the next step tackles.
- A learner may believe: “The swap can be done in two lines.” Respond: Copying one value over the other loses a value; a third place, Temp, holds it.
On the board or with the pen
- Draw the five boxes and use an actual spare card as Temp to demonstrate the three-line swap of 5 and 1. Then fill a table of Pass, Swaps and Array after the pass.
What learners should notice
- The array does not change in passes 3 and 4.
Checking understanding: The why-index-four check: the first element and the outer loop options are the two common wrong reasons; the bubble-passes table checks that pupils can write the array after each pass.
Depending on the answers
- If pupils choose the outer-loop option: ask them to write Numbers[Index + 1] with Index = 5 and say what it refers to.
- If pupils write the wrong array after pass 1: trace pass 1 with the StepThrough and compare each step.
Support
- Provide the first row of the bubble-passes table and the StepThrough open for reference.
Stretch
- How many comparisons does the sort make in total on five items? On ten?
English as an additional language
- Check temporary and overwrite; show two cups of different drinks and a third empty cup to swap them.
In the lesson window
- Check your understanding: Why does the inner loop run Index from 1 to 4 and not from 1 to 5, when the array has five elements?
5. Stopping when nothing moves Explain 12 min
On the lesson window now
Purpose: Pupils work out how a program can tell the list is sorted, then trace a flag version and say how many passes an already sorted list needs.
Ask
- What does a pass with no swaps tell you about the list?
- How could the program notice and stop?
- How many passes does the flag version make on 1 2 3 4 5?
Responses to expect
- Every neighbouring pair is in order, so the whole list is
- A flag set to FALSE at the start of each pass and TRUE on a swap
- One
Misconceptions to challenge
- A learner may believe: “A sorted list needs no pass at all.” Respond: The program needs one pass to find out that nothing moves.
- A learner may believe: “The flag version always makes four passes.” Respond: That was the first version; the flag stops the loop.
- A learner may believe: “Swapped is set to FALSE once, before the REPEAT.” Respond: It must be reset at the start of every pass, or it would stay TRUE.
- A learner may believe: “The number of passes equals the number of items.” Respond: It depends on the flag; sorted lists finish after one pass.
On the board or with the pen
- Write the flag version and trace 5 1 4 2 8 with columns Pass, Swaps, Swapped at the end, Stop?; then trace 1 2 3 4 5 and mark the single pass.
Checking understanding: The flag-passes check: 4 is the first version's count and 5 is the number of items; look for pupils who say the flag decides.
Depending on the answers
- If pupils choose 4 or 5: ask what Swapped is at the end of the first pass on 1 2 3 4 5, and what UNTIL then does.
- If pupils are secure: ask for a list of five that needs the most passes with the flag version, and say how many.
Support
- Provide the trace table with the first two rows filled in.
Stretch
- What happens if Swapped ← FALSE is moved to before the REPEAT?
English as an additional language
- Check flag and notice; use a flag raised on a swap.
In the lesson window
- Think it through: In the table, passes 3 and 4 made no swaps. What does a pass with no swaps tell you about the list? How could the program notice that and stop early?
- Check your understanding: The flag version is run on a list that is already in order: 1 2 3 4 5. How many passes does it make?
6. Spot the mistake Apply 8 min
On the lesson window now
Purpose: Pupils trace a swap with no temporary variable to see both elements become the same, and find why a sort comes out largest first.
Ask
- The array holds 5 and 1 and the swap runs once: what do the first two elements hold, and why?
- What causes the list to end up from largest to smallest, and what is the one-character change?
Responses to expect
- 1 and 1, because the first line overwrites the 5
- The condition swaps when the left one is smaller; change < to >
Misconceptions to challenge
- A learner may believe: “The two lines swap the values.” Respond: Follow the lines one at a time: after the first, both hold 1.
- A learner may believe: “Nothing changes because the two lines cancel.” Respond: The condition is true, so they run; trace them.
- A learner may believe: “The inner loop is going the wrong way.” Respond: The loop is fine; the comparison decides the order.
- A learner may believe: “A missing Temp would reverse the list neatly.” Respond: It loses values, not reverses them.
On the board or with the pen
- Write 5 and 1 in two boxes and update them after each line of Sam's swap, crossing out the old values.
Checking understanding: Both questions have wrong options that match common beliefs; the descending answer shows whether pupils connect the comparison to the order.
Depending on the answers
- If pupils choose 1 and 5: run the two lines on the board with boxes and ask what the first line did to the 5.
- If pupils are quick: ask them to write the three-line correct swap and trace it for 5 and 1.
Support
- Provide two boxes drawn on paper for pupils to update after each line.
In the lesson window
- Apply it: The array holds 5 and 1 in its first two elements, and the swap above is carried out once. What do the first two elements hold afterwards, and why?
- Apply it: What is the cause, and what is the one-character change that sorts from smallest to largest?
7. Write one yourself Apply 12 min
On the lesson window now
Purpose: Pupils write a linear search of five titles that also counts comparisons and say what it outputs for Emma and for Maus.
Ask
- Write the search with a counter of titles compared.
- What does it output for Emma and for Maus?
Responses to expect
- Found and Position as before plus Checked ← 0 and Checked ← Checked + 1 inside the loop
- Emma at position 4 after 4 compared; Maus not in the catalogue after 5 compared
Misconceptions to challenge
- A learner may believe: “The counter goes after the loop.” Respond: Set it to 0 before the loop and add 1 inside, each time a title is compared.
- A learner may believe: “The loop must always check all five.” Respond: It stops when Found is TRUE, so Emma needs only four.
- A learner may believe: “Position goes up even after a match.” Respond: Position goes up only in the ELSE, so it stays at the match.
On the board or with the pen
- Write the program as pupils dictate it, then trace Emma and Maus in a table with Position, Titles[Position], Found and Checked.
Checking understanding: Collect the programs: look for the flag, the loop condition with both tests, the counter set before the loop and the two outputs.
Depending on the answers
- If pupils output Position for a missing title: ask what Position holds at the end for a title that is missing and why the program must use Found.
- If pupils finish early: ask them to also output whether the title was in the first half of the list.
Support
- Provide the program from the Tom example with the names changed and ask pupils to add the counter.
Stretch
- Change the program to count how many titles match the target in a list with repeats, and keep searching to the end.
In the lesson window
- Think it through: Write pseudocode that does a linear search of Titles for a title typed by the user. It should also count how many titles were compared, and then output either the position found, or a message that the title is not in the catalogue, with the number of titles compared. What does it output for Emma, and for Maus?
8. Show what you know Consolidate 10 min
On the lesson window now
Purpose: Pupils explain both algorithms with a list of their own and apply one pass of a bubble sort to a new list before the summary.
Ask
- Explain how a linear search and a bubble sort work with a short list of your own.
- What does 3 9 2 7 look like after exactly one pass?
Responses to expect
- Search checks each item in turn; sort compares neighbours and swaps
- 3 2 7 9
Misconceptions to challenge
- A learner may believe: “2 3 7 9 after one pass.” Respond: Do the pass: 3 and 9 no swap, 9 and 2 swap, 9 and 7 swap. The 3 and 2 are still the wrong way round.
- A learner may believe: “Nothing swaps because the first pair is in order.” Respond: The pass continues past the first pair: 9 and 2 is out of order.
Checking understanding: Collect the explanations: look for worst case, neighbour comparison, and what one pass does.
Depending on the answers
- If pupils choose 2 3 7 9: ask them to do the pass with number cards and compare the result with a sorted list.
- If several are unsure of passes: begin the next lesson by sorting 6 2 5 1 on the board one pass at a time.
In the lesson window
- Think it through: Explain to a friend how a linear search works and how a bubble sort works, using a short list of your own. Say how many items a linear search might have to check, and what one pass of a bubble sort does.
- Apply it: The list 3 9 2 7 is sorted into ascending order by a bubble sort. What does the list look like after exactly one pass?
Lesson recap Closing
On the lesson window now
On screen: the lesson’s objectives again; Next adds the closing question, which asks the class to explain each one in their own words without looking back. It says nothing about what anyone has learnt: use the answers to decide what to revisit.
Points to listen for
- A linear search checks items in turn from the first until it finds the target or reaches the end; the worst case checks every item.
- A bubble sort compares neighbours and swaps those the wrong way round; after each pass the largest remaining value is at the end.
- A swap needs a temporary variable; the inner loop goes to N - 1 because it compares Index with Index + 1.
- A flag lets the sort stop when a pass makes no swaps.
- Changing the comparison reverses the order of the sort; one pass does not sort a list.
Consolidation
- A linear search checks items in turn from the first until it finds the target or reaches the end; the worst case checks every item.
- A bubble sort compares neighbours and swaps those the wrong way round; after each pass the largest remaining value is at the end.
- A swap needs a temporary variable; the inner loop goes to N - 1 because it compares Index with Index + 1.
- A flag lets the sort stop when a pass makes no swaps.
- Changing the comparison reverses the order of the sort; one pass does not sort a list.