Study Guide
Linear Search and Bubble Sort
Two standard algorithms for lists: a linear search, which looks at each item in turn until it finds the one wanted, and a bubble sort, which puts a list in order by swapping neighbours, traced pass by pass and improved with a flag that stops it early.
Lesson 5.11 Algorithms and Programming
For: Cambridge IGCSE Computer Science learners, or Key Stage 3 learners who have met loops, selection and arrays (about ages 13 to 14)
Stage: Think
Is this name on the list?
A fictional school club has a clipboard with six names written down in the order the pupils joined: Zoe, Raj, Mei, Tom, Ana and Leo. The names are in no kind of order. A teacher asks, “Is Eve in the club?”
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?
- Hint 1: You cannot jump to the right place, because the names are in no order.
- Hint 2: What if Eve is not on the list at all?
Show a model answer
Read the names from the top, one at a time, comparing each with “Eve”, and stop as soon as one matches. If none does, you can only be sure after reading every name, so the most you might read is all six. With no order to help, there is no shortcut.
Stage: Discover
Looking at each item in turn
Checking each item in turn, from the first, until the item is found or the list runs out, is a linear search. It works on any list, in any order. The program below keeps a flag, Found, which says whether the target has been found, and a Position, which says which item is being looked at. The array has been filled with the six names above, in order.
DECLARE Names : ARRAY[1:6] OF STRING
DECLARE Found : BOOLEAN
Names[1] ← "Zoe"
Names[2] ← "Raj"
Names[3] ← "Mei"
Names[4] ← "Tom"
Names[5] ← "Ana"
Names[6] ← "Leo"
INPUT Target
Found ← FALSE
Position ← 1
WHILE Found = FALSE AND Position <= 6 DO
IF Names[Position] = Target
THEN
Found ← TRUE
ELSE
Position ← Position + 1
ENDIF
ENDWHILE
IF Found = TRUE
THEN
OUTPUT Target, " is at position ", Position
ELSE
OUTPUT Target, " is not on the list"
ENDIFThe loop continues while the item has not been found and there are still items left. When a match is found, Found becomes TRUE, Position stays where it is, and the loop stops. Trace a search for Tom.
| Position | Names[Position] | Equal to Tom ? | Found after this pass |
|---|---|---|---|
| 1 | Zoe | No | FALSE |
| 2 | |||
| 3 | |||
| 4 |
Show the completed table
| Position | Names[Position] | Equal to Tom ? | Found after this pass |
|---|---|---|---|
| 1 | Zoe | No | FALSE |
| 2 | Raj | No | FALSE |
| 3 | Mei | No | FALSE |
| 4 | Tom | Yes | TRUE |
The program outputs Tom is at position 4. The first row is given as an example. Four names were checked.
Check your understanding
Show the answer
Answer: B. 1000, because the name could only be ruled out by checking every one.
The worst case for a linear search is when the item is last or not there at all, and it checks every item.
A linear search does not need the list to be in order, and putting the list in order does not make this algorithm faster. The best case is that the item is first, so only one check is needed. The worst case is that the item is last or missing, so every item is checked. Searching a sorted list in a cleverer way is a different algorithm, not taught here.
Do not confuse: Searching and sorting
- What is the job?Search
- Find out whether an item is in a list, and where. The list is left as it was.Is Tom on the clipboard? At which position?
- What is the job?Sort
- Rearrange the items into order, such as smallest to largest. The list changes.Put the heights in order from shortest to tallest.
A search does not change the list; a sort does.
Stage: Predict
Putting a list in order
Many jobs need a list in order, such as showing scores from lowest to highest. Imagine five fictional pupils standing in a row, each holding a card: 5, 1, 4, 2 and 8. They are told: “You may compare only two neighbours at a time, and swap them if the pupil on the left has the bigger number. Start at the left, and walk along the row once.”
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?
- Hint 1: Try it with five coins or pieces of paper numbered 5, 1, 4, 2, 8.
- Hint 2: When two big numbers meet, the bigger one carries on moving right.
Show what happens
The 8 stays at the right-hand end; it is the biggest, so it is never swapped to the left. The 5 meets 1, 4 and 2 in turn, and is bigger than each, so it is swapped along until it reaches the 8, and ends up in the fourth place. The row is not yet in order, but the biggest value has reached its place.
This is a bubble sort: pass along the list comparing neighbours, and swap any pair that is the wrong way round. One walk along the list is a pass. After each pass the biggest value not yet in place has moved, like a bubble rising, to the end. Here is the first pass on 5, 1, 4, 2, 8.
Each step compares one pair of neighbours and swaps them if the left one is bigger.
Compare items 1 and 2
Step 1 of 4: 5 and 1
5 is greater than 1, so they are swapped. The list is now 1 5 4 2 8.
Compare items 2 and 3
Step 2 of 4: 5 and 4
5 is greater than 4, so they are swapped. The list is now 1 4 5 2 8.
Compare items 3 and 4
Step 3 of 4: 5 and 2
5 is greater than 2, so they are swapped. The list is now 1 4 2 5 8.
Compare items 4 and 5
Step 4 of 4: 5 and 8
5 is not greater than 8, so nothing is swapped. The pass is over, and the list is 1 4 2 5 8.
Technical detail: Three swaps were made in this pass. The largest value, 8, is in its final place at the end.
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?
- Hint 1: Compare 1 and 4 first.
Show a model answer
1 and 4: no swap. 4 and 2: swap, giving 1 2 4 5 8. 4 and 5: no swap. 5 and 8: no swap. After pass 2 the list is 1 2 4 5 8 and one swap was made. It is already in order, but the program does not know that yet.
Stage: Explain
Writing the bubble sort
- Store the list in an array.
Numbersis anARRAY[1:5] OF INTEGERholding 5, 1, 4, 2 and 8. - One pass. A FOR loop with the index running over the pairs. A pair is
Numbers[Index]andNumbers[Index + 1], so Index only goes up to 4: at 5,Numbers[Index + 1]would beNumbers[6], which does not exist. - Swap when the left one is bigger.
IF Numbers[Index] > Numbers[Index + 1]. - The swap needs a spare place. Copy one value into a temporary variable,
Temp, first. WritingNumbers[Index] ← Numbers[Index + 1]straight away would overwrite the left value, and it would be lost for ever. - Repeat the pass. With 5 items, at most 4 passes are needed to put every item in place, so the pass is inside an outer loop of 4.
FOR Pass ← 1 TO 4
FOR Index ← 1 TO 4
IF Numbers[Index] > Numbers[Index + 1]
THEN
Temp ← Numbers[Index]
Numbers[Index] ← Numbers[Index + 1]
Numbers[Index + 1] ← Temp
ENDIF
NEXT Index
NEXT PassCheck your understanding
Show the answer
Answer: A. Because Numbers[Index + 1] would be Numbers[6] at Index = 5, outside the bounds.
For a list of N items there are N - 1 neighbouring pairs.
| Pass | Swaps made | Array after the pass |
|---|---|---|
| Start | - | 5 1 4 2 8 |
| 1 | 3 | |
| 2 | ||
| 3 | ||
| 4 |
Show the completed table
| Pass | Swaps made | Array after the pass |
|---|---|---|
| Start | - | 5 1 4 2 8 |
| 1 | 3 | 1 4 2 5 8 |
| 2 | 1 | 1 2 4 5 8 |
| 3 | 0 | 1 2 4 5 8 |
| 4 | 0 | 1 2 4 5 8 |
The list is in order after pass 2. Passes 3 and 4 make no swaps, and are wasted work.
One pass does not sort a list. It only moves the largest value not yet in place to its end. A list of N items may need up to N - 1 passes, though, as in the table, it may be in order sooner.
Stage: Explain
Stopping when nothing moves
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?
- Hint 1: What would the program have to remember during a pass?
Show a model answer
A pass with no swaps means every neighbouring pair is already in order, so the whole list is in order. The program can remember whether any swap happened during the pass, using a flag set to FALSE at the start of the pass and to TRUE whenever a swap is made. When a pass finishes with the flag still FALSE, it can stop.
REPEAT
Swapped ← FALSE
FOR Index ← 1 TO 4
IF Numbers[Index] > Numbers[Index + 1]
THEN
Temp ← Numbers[Index]
Numbers[Index] ← Numbers[Index + 1]
Numbers[Index + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT Index
UNTIL Swapped = FALSESwapped is set to FALSE at the start of every pass, and to TRUE whenever a swap is made. A REPEAT … UNTIL loop makes a pass first and then tests, which is what is wanted, since at least one pass is always needed. The loop stops when a pass makes no swaps.
| Pass | Swaps made | Swapped at the end of the pass | Does the loop stop? |
|---|---|---|---|
| 1 | 3 | TRUE | No |
| 2 | |||
| 3 |
Show the completed table
| Pass | Swaps made | Swapped at the end of the pass | Does the loop stop? |
|---|---|---|---|
| 1 | 3 | TRUE | No |
| 2 | 1 | TRUE | No |
| 3 | 0 | FALSE | Yes |
The first row is given as an example. The flag version finishes after 3 passes; the first version always made 4.
Check your understanding
Show the answer
Answer: C. 1, because the first pass makes no swaps, so the flag stays FALSE.
Even an already sorted list needs one pass, to find out that nothing moves.
Stage: Apply
Spot the mistake
Sam (fictional) writes the swap in a bubble sort like this:
IF Numbers[Index] > Numbers[Index + 1]
THEN
Numbers[Index] ← Numbers[Index + 1]
Numbers[Index + 1] ← Numbers[Index]
ENDIFApply it
Show the answer
Answer: D. 1 and 1, because the first line overwrites the 5 before it can be copied.
A swap uses three lines: save one value in a temporary variable, copy the other across, then copy the saved value.
Priya (fictional) runs a bubble sort on 5, 1, 4, 2 and 8, but the list ends up as 8 5 4 2 1, from largest to smallest. Her condition is IF Numbers[Index] < Numbers[Index + 1].
Apply it
Show the answer
Answer: C. The condition swaps when the left one is smaller; changing < to > fixes it.
Changing the comparison sign reverses the order of a sort.
Stage: Apply
Write one yourself
A fictional library has an array Titles of five book titles in no order, filled as Titles[1] ← “Holes”, Titles[2] ← “Dune”, Titles[3] ← “Matilda”, Titles[4] ← “Emma” and Titles[5] ← “Wonder”. A librarian types a title to look for.
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?
Work this out on paper or the board first. Nothing here is marked: compare yours with the model answer.
- Hint 1: Use a flag and a position, as in the Tom example, and add a counter that goes up each time a title is compared.
- Hint 2: Remember to set the counter to 0 before the loop.
Show a model answer
DECLARE Titles : ARRAY[1:5] OF STRING
DECLARE Found : BOOLEAN
Titles[1] ← "Holes"
Titles[2] ← "Dune"
Titles[3] ← "Matilda"
Titles[4] ← "Emma"
Titles[5] ← "Wonder"
OUTPUT "Title to find?"
INPUT Target
Found ← FALSE
Position ← 1
Checked ← 0
WHILE Found = FALSE AND Position <= 5 DO
Checked ← Checked + 1
IF Titles[Position] = Target
THEN
Found ← TRUE
ELSE
Position ← Position + 1
ENDIF
ENDWHILE
IF Found = TRUE
THEN
OUTPUT Target, " is at position ", Position
ELSE
OUTPUT Target, " is not in the catalogue"
ENDIF
OUTPUT "Titles compared: ", CheckedFor Emma the search finds it at position 4 after comparing four titles, so it outputs Emma is at position 4 and Titles compared: 4. For Maus the title is not there, so all five are compared: Maus is not in the catalogue and Titles compared: 5. The counter is set to 0 before the loop and goes up inside it.
Go deeper The same algorithms in Python
names = ["Zoe", "Raj", "Mei", "Tom", "Ana", "Leo"]
target = "Tom"
found = False
position = 0
while not found and position < len(names):
if names[position] == target:
found = True
else:
position = position + 1
if found:
print(target, "is at position", position + 1)
else:
print(target, "is not on the list")
numbers = [5, 1, 4, 2, 8]
swapped = True
while swapped:
swapped = False
for index in range(len(numbers) - 1):
if numbers[index] > numbers[index + 1]:
temp = numbers[index]
numbers[index] = numbers[index + 1]
numbers[index + 1] = temp
swapped = True
print(numbers)- Python counts from 0, so the search starts with
position = 0, and the position is shown asposition + 1.range(len(numbers) - 1)gives the indexes 0 to 3, the four pairs of five items. - This program prints
Tom is at position 4and then[1, 2, 4, 5, 8]. Python has no REPEAT … UNTIL, so awhile swapped:loop that starts withswapped = Truedoes the same job. - Python can swap in one line,
numbers[index], numbers[index + 1] = numbers[index + 1], numbers[index], and has built-in tools (in,.index()andsorted()). The exam wants the algorithms written out, and they show how the built-in tools work. - A bubble sort is slow on long lists, because the number of comparisons grows roughly with the square of the number of items, so real programs use faster sorting methods. It is taught because it is simple to follow.
Stage: Consolidate
Show what you know
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.
Show a model answer
A good answer says that a linear search looks at each item in turn, from the first, until it finds the target or reaches the end, so in the worst case (the target is last or missing) it checks every item. A bubble sort passes along the list comparing neighbouring pairs and swapping any that are the wrong way round, so each pass moves the largest remaining value to its place at the end; it repeats until a pass makes no swaps, which shows that the list is in order.
Apply it
Show the answer
Answer: B. 3 2 7 9, because 9 is swapped with 2 and then with 7, and 3 is left alone.
One pass places the largest value; the rest of the list may still be out of order.
- A linear search checks the items in turn from the first until it finds the target or reaches the end. It works on any list. In the worst case, when the target is last or missing, it checks every item.
- A bubble sort passes along the list comparing neighbours and swapping any pair the wrong way round. After each pass the largest value not yet placed is at the end. A list of N items needs at most N - 1 passes.
- A swap needs a temporary variable. The inner loop of a bubble sort goes to N - 1, because it compares
IndexwithIndex + 1. - A flag that records whether any swap happened lets a bubble sort stop as soon as a pass makes none.
- Usual faults: a swap with no temporary variable, a loop that runs past the end of the array, a comparison the wrong way round, and thinking one pass sorts a list.
Sources and scope
- What this lesson is. The eleventh lesson of the Algorithms and Programming module, written for this site. It covers the linear search and bubble sort of point 7.4 of Cambridge IGCSE Computer Science 0478 (2026 to 2028, version 6). Its curriculum links are provisional and imply no review or endorsement by any examination board.
- Original material. The club clipboard, the line of pupils, the library and Sam and Priya are fictional, written for this lesson. The pseudocode follows the layout of the syllabus’s pseudocode guide, and every output and every pass was worked out by hand and checked with an equivalent Python program.
- Simplified on purpose. The lists are short and are sorted into ascending order. Bubble sort is written with a fixed inner loop each pass (a common refinement stops each pass one item earlier, which is not taught here). Binary search, other sorts and measuring how fast an algorithm grows are not taught.
- Left to later lessons. Validation and verification, test data and writing algorithms for longer scenarios.
A sequence of precise steps that solves a problem or completes a task.
A fixed-size structure that stores several values of the same data type under one name, each found by its index.
A search of a sorted list that checks the middle item and, by seeing whether the target is bigger or smaller, throws away half of the list each time.
A sort that passes along a list again and again, comparing neighbouring items and swapping any that are the wrong way round, until the list is in order.
An expression that is either true or false, such as Age >= 12, used to decide what a program does next.
A loop that repeats a fixed number of times, known before it starts. In pseudocode it is a FOR … NEXT loop.
The number, written in square brackets after an array’s name, that says which element is meant.
A search that checks the items of a list one at a time, from the first, until it finds the target or reaches the end.
A set of instructions that is repeated, either a fixed number of times or until a condition says to stop.
A precise but language-independent way of writing an algorithm, with set keywords such as IF, WHILE and OUTPUT, that is not tied to any one programming language.
A high-level programming language written as text, popular for learning and for real work, in which indentation shows which lines belong together.
A named place in memory that stores a value which can change while a program runs.
Your progress on this lesson
Saved in this browser only. It is not sent anywhere, does not follow you to another device, and is lost if you clear this site’s data.
This browser is not allowing the site to save progress, so it will be forgotten when you leave the page.