IB Computer Science · B2 · Programming
B2.4 Programming algorithms
Describe the steps of a linear search, explain how a bubble sort works, trace simple algorithms and compare the efficiency of two basic algorithms.
1/6A linear search checks each item in turn
- A linear search checks each item in turn
- A trace table lets you follow an algorithm by hand
- Bubble sort swaps neighbouring items until the list is ordered
- Tracing a bubble sort shows how each pass works
- Efficiency describes how the work grows with list size
- Binary search needs fewer comparisons but requires sorted data
- Check your recall
- Practice: 10 questions
Part 1 of 6: A linear search checks each item in turn
Suppose you look for one name on an unsorted guest list. You start at the top and read each name until you find a match or reach the end. The name you want is the target, and this method is a linear search.
- Set the position to the first item.
- Compare the item at that position with the target.
- If they match, report the position and stop.
- Otherwise, move to the next position.
- If the end is reached without a match, report that the target is absent.
The list does not need to be sorted. The method is simple and always correct, but it can be slow on long lists.
Key term
linear search
A linear search is an algorithm that examines list items one at a time in order, and works on sorted or unsorted data.
Part 2 of 6: A trace table lets you follow an algorithm by hand
Before moving on to sorting, you need a way to check what an algorithm does. A trace table records the value of each variable after every step. Use one column per variable and one row per change. It lets you test an algorithm without running it.
Worked example
Trace a linear search
- Position 0 holds 7. It is not 9, so move to the next position.
- Position 1 holds 3. It is not 9, so move on again.
- Position 2 holds 9. This matches the target, so the search stops.
Answer: The search returns position 2 after 3 comparisons.
Tracing also locates faults. If the output is wrong, find the first row where a value looks wrong. The fault lies at or just before that step.
Key term
trace table
A trace table is a table that records the value of every variable after each step of an algorithm.

Quick check
One question on the part you just read
Easy
Show answer and explanation
Answer: A · Worked explanation
Part 3 of 6: Bubble sort swaps neighbouring items until the list is ordered
Searching is easier on ordered data, so now consider how to sort a list. A bubble sort compares each pair of neighbouring items. If a pair is in the wrong order, the two items swap. Here the list is sorted in ascending order, smallest first.
One full run through the list is a pass. After the first pass, the largest item has moved to the end. Each later pass places the next largest item.
The algorithm stops when a whole pass makes no swaps. This final pass confirms that the list is in order.
Key terms · tap one for its definition
bubble sort
A bubble sort is a sorting algorithm that repeatedly compares neighbouring items and swaps them when out of order, until no swaps are needed.
pass
A pass is one complete run through the list in a bubble sort, comparing each neighbouring pair once.
Part 4 of 6: Tracing a bubble sort shows how each pass works
Now apply the trace method to a short list. To swap two items, a program needs a temporary variable. It stores the first value, copies the second value across, then places the stored value in the second position. Check each pass against one rule: compare neighbours, and swap if they are out of order.
Worked example
Trace a bubble sort
- Pass 1: swap 5 and 3, keep 5 and 8, then swap 8 and 1. The list is 3, 5, 1, 8.
- Pass 2: keep 3 and 5, swap 5 and 1, then keep 5 and 8. The list is 3, 1, 5, 8.
- Pass 3: swap 3 and 1, then keep the other pairs. The list is 1, 3, 5, 8.
- Pass 4: no pair is out of order, so no swaps happen and the algorithm stops.
Answer: The sorted list is 1, 3, 5, 8. Three passes make swaps and a fourth pass confirms the order.
Notice that the largest item reaches the end in the first pass. Later passes can ignore the items already in place. A program that stops after a pass with no swaps finishes early on lists that are nearly sorted.

Quick check
One question on the part you just read
Easy
Show answer and explanation
Answer: C · Worked explanation
Part 5 of 6: Efficiency describes how the work grows with list size
Both algorithms give correct results, so the next question is how much work each does. Efficiency describes how the work an algorithm needs grows as the input grows. A simple measure counts comparisons.
The worst case is the input that makes the algorithm do the most work. For a list of items, a linear search needs up to comparisons. This happens when the target is last or absent.
Bubble sort grows faster, roughly with . Doubling the list size about quadruples the comparisons.
Key terms · tap one for its definition
efficiency
The efficiency of an algorithm is a measure of the time or number of steps it needs, usually compared as input size grows.
worst case
The worst case is the input of a given size that makes an algorithm perform the greatest number of steps.
Part 6 of 6: Binary search needs fewer comparisons but requires sorted data
Linear search is not the only way to find an item. A binary search compares the target with the middle item of a sorted list. It then discards the half that cannot hold the target and repeats on the other half.
Each step halves the remaining items. A sorted list of 1000 items needs at most about 10 comparisons, while a linear search could need 1000.
Linear search compared with binary search
- Feature
- List must be sorted
- Linear search
- No
- Binary search
- Yes
- Feature
- Worst-case comparisons
- Linear search
- Binary search
- about
- Feature
- Best suited to
- Linear search
- Short or unsorted lists
- Binary search
- Long sorted lists
Key term
binary search
A binary search is an algorithm that finds a target in a sorted list by repeatedly halving the part still to be searched.
Check your recall[14 marks]
6 written questions. Answer each one in your head or on paper, then open the mark scheme.
- 1.Describe[3 marks]
Describe the steps of a linear search for a target in a list.
Show mark schemeHide mark scheme
Model answer
Start at the first item and compare it with the target. If it matches, report its position and stop; otherwise move to the next item. If the end is reached without a match, report that the target is absent.
- 1 mark for starting at the first item and comparing each item with the target in turn
- 1 mark for stopping and reporting the position when a match is found
- 1 mark for reporting that the target is absent if the end is reached without a match
- 2.Explain[3 marks]
Explain how a bubble sort puts a list into ascending order.
Show mark schemeHide mark scheme
Model answer
It compares each pair of neighbouring items in a pass and swaps any pair that is out of order. After each pass the next largest item is in its final place. It repeats passes until a pass makes no swaps.
- 1 mark for comparing neighbouring items and swapping those in the wrong order
- 1 mark for repeating passes so that the largest remaining item moves to the end
- 1 mark for stopping when a pass makes no swaps
- 3.Determine[2 marks]
Determine the list after the first pass of a bubble sort on 4, 2, 7, 1 in ascending order.
Show mark schemeHide mark scheme
Model answer
Swap 4 and 2 to give 2, 4, 7, 1. Keep 4 and 7. Swap 7 and 1. The list is 2, 4, 1, 7.
- 1 mark for comparing neighbouring pairs and swapping 4 and 2, then 7 and 1, while leaving 4 and 7 in place
- 1 mark for giving the list 2, 4, 1, 7
- 4.Compare[3 marks]
Compare linear search and binary search.
Show mark schemeHide mark scheme
Model answer
Linear search works on unsorted lists, but binary search needs a sorted list. Linear search may need up to comparisons. Binary search needs about comparisons, so it is faster on long sorted lists.
- 1 mark for stating that linear search works on unsorted lists but binary search needs a sorted list
- 1 mark for stating that linear search may need up to comparisons
- 1 mark for stating that binary search needs about comparisons, so it is faster on long sorted lists
- 5.Outline[2 marks]
Outline why a trace table is useful when checking an algorithm.
Show mark schemeHide mark scheme
Model answer
It records each variable’s value after every step, so the algorithm can be tested by hand. The first row with a wrong value shows where a fault lies.
- 1 mark for stating that it records the value of each variable after each step
- 1 mark for stating that it helps locate where a fault occurs
- 6.Calculate[1 mark]
Calculate the largest number of comparisons a linear search needs on a list of 250 items.
Show mark schemeHide mark scheme
Model answer
The worst case is 250 comparisons, when the target is last or absent.
- 1 mark for giving 250

Practice this topic
10 quick-fire multiple-choice questions, easy to hard. Tap an answer to see if you're right and the worked explanation. (The written questions with mark schemes are under “Check your recall” above.)
0 right0 of 10 answered
Includes the 2 quick checks in the note above.
Easy[1 mark]
Show answer and explanation
Answer: B · Worked explanation
MediumDetermine[1 mark]
Show answer and explanation
Answer: A · Worked explanation
MediumDetermine[1 mark]
Show answer and explanation
Answer: D · Worked explanation
MediumCalculate[1 mark]
Show answer and explanation
Answer: C · Worked explanation
MediumCalculate[1 mark]
Show answer and explanation
Answer: B · Worked explanation
HardPredict[2 marks]
Show answer and explanation
Answer: A · Worked explanation
HardDetermine[2 marks]
Show answer and explanation
Answer: D · Worked explanation
HardCompare[2 marks]
Show answer and explanation
Answer: C · Worked explanation