Linear Search and Bubble Sort: The Full IGCSE Computer Science Guide

Linear search and bubble sort for IGCSE Computer Science: the exact algorithm steps, pseudocode and worked traces, mark-scheme style.

You can explain a bubble sort perfectly out loud. It compares pairs, swaps the wrong ones, and keeps going until nothing moves anymore. Then you sit down to write the trace table in an exam and either freeze on how many passes to show, or write out every single comparison when the mark scheme only wanted the list at the end of each pass. That's not a knowledge gap. It's not knowing what CIE actually rewards you for writing down.

After marking a lot of scripts on this topic, the pattern is always the same. Students understand the idea perfectly, then lose marks on the pseudocode syntax, the vocabulary (pass versus swap), or by over-explaining a step the mark scheme was never going to reward anyway.

This guide covers both algorithms the way CIE actually marks them: full pseudocode, working Python, and a pass-by-pass trace table in the exact format examiners want to see.

Quick checklist before you sit a question on this topic:

Can you say, without hesitating, why a linear search doesn't need sorted data and a binary search does?
Do you know CIE's actual pseudocode keywords (OUTPUT, INPUT, DECLARE, IF...THEN...ENDIF), not print() and brackets?
For a bubble sort trace, are you writing the list after each pass, not every individual comparison?
Do you know the difference between a "pass" and a "swap"?
Can you explain, in one sentence, why a temp variable is needed to swap two values in pseudocode?

What Are Linear Search and Bubble Sort in IGCSE Computer Science?

Linear search and bubble sort are the two core algorithms taught under "Algorithm Design and Problem-Solving" in Cambridge (CIE) IGCSE Computer Science (0478/0984). A linear search finds a target value by checking every item in a list, one after another, until it finds a match or runs out of items. A bubble sort puts a list into order by repeatedly comparing adjacent pairs of values and swapping them if they're the wrong way round.

Neither algorithm is conceptually hard. That's exactly why they're a trap.

How Does a Linear Search Work?

A linear search starts at the first item in a list, checks it against the target value, and stops immediately if it matches. If it doesn't match, the search moves to the next item and repeats, continuing until either a match is found or every item has been checked with no match. Crucially, a linear search doesn't require the data to be sorted first. It works on a list in any order, which is the main reason CIE asks you to compare it with binary search, a separate topic that does need sorted data.

Step

Instruction

Check the first value in the list

If it matches the target, stop: the search is complete

If it doesn't match, move to the next value and check it

Repeat step 2 and 3 until the target is found or every value has been checked

You won't be asked to hand-trace a linear search step by step in the exam the way you will for a bubble sort. CIE expects you to understand the process and state its advantages and disadvantages, not walk through every comparison on paper.

How Do You Write a Linear Search in Pseudocode?

Here's a linear search over a five-item array, written in CIE-style pseudocode:

DECLARE data : ARRAY[1:5] OF INTEGER

DECLARE target : INTEGER

DECLARE found : BOOLEAN

data ← [12, 7, 34, 9, 21]

target ← 34

found ← FALSE

FOR index ← 1 TO 5

IF data[index] = target THEN

found ← TRUE

OUTPUT "Target found at position ", index

ENDIF

NEXT index

IF found = FALSE THEN

OUTPUT "Target not found"

ENDIF

And the same logic in Python:

data = [12, 7, 34, 9, 21]

target = 34

found = False

for index in range(len(data)):

if data[index] == target:

found = True

print("Target found at position", index)

break

if not found:

print("Target not found")

Worked trace: searching for 34 in [12, 7, 34, 9, 21]. Position 1 (12), no match. Position 2 (7), no match. Position 3 (34), match, search stops.

Three comparisons were needed, not five, because a linear search stops the moment it finds the target. That's a detail worth stating explicitly if a question asks how many comparisons were made.

What Are the Advantages and Disadvantages of a Linear Search?

Advantages

Disadvantages

Simple to implement and understand

Slow on large datasets: worst case checks every single item

Works on data in any order (no sorting required)

Inefficient compared with binary search when data is already sorted

Doesn't need extra memory or preprocessing

Best case (item 1) and worst case (item not present, or last item) are far apart in speed

The "works on unsorted data" point is the one students most often forget to state. It's usually worth its own mark, because it's the direct trade-off against binary search.

How Does a Bubble Sort Work?

A bubble sort begins at the start of a list, compares each pair of adjacent values, and swaps them if they're in the wrong order. One full sweep from the first item to the last is called a pass. The algorithm keeps making passes until a complete pass produces no swaps at all. At that point, the list is sorted and the algorithm stops.

Step

Instruction

Compare the first two values in the list

If they're in the wrong order, swap them

Move along and compare the next pair

Repeat steps 2 and 3 until you reach the end of the list (this completes one pass)

If any swaps were made during that pass, start a new pass from the beginning

If no swaps were made, stop: the list is sorted

How Do You Write a Bubble Sort in Pseudocode?

DECLARE nums : ARRAY[1:5] OF INTEGER

nums ← [8, 3, 5, 1, 9]

DECLARE n : INTEGER

n ← 5

DECLARE swapped : BOOLEAN

swapped ← TRUE

WHILE swapped = TRUE

swapped ← FALSE

FOR i ← 1 TO n - 1

IF nums[i] > nums[i + 1] THEN

DECLARE temp : INTEGER

temp ← nums[i]

nums[i] ← nums[i + 1]

nums[i + 1] ← temp

swapped ← TRUE

ENDIF

NEXT i

n ← n - 1

ENDWHILE

FOR i ← 1 TO 5

OUTPUT nums[i]

NEXT i

And in Python:

nums = [8, 3, 5, 1, 9]

n = len(nums)

swapped = True

while swapped:

swapped = False

for i in range(n - 1):

if nums[i] > nums[i + 1]:

nums[i], nums[i + 1] = nums[i + 1], nums[i]

swapped = True

n -= 1

print(nums)

The one line examiners specifically look for in the pseudocode version is the swap using a temporary variable (temp). Writing nums[i] ← nums[i+1] ← nums[i] without a holding variable is a common error that loses the accuracy mark, even when the logic is otherwise right.

Worked Example: Tracing a Bubble Sort Pass by Pass

Take the unsorted list [8, 3, 5, 1, 9]. Here's exactly what CIE wants to see: the state of the list at the end of each pass, not every individual comparison.

Pass 1: Compare 8,3 → swap → [3,8,5,1,9]. Compare 8,5 → swap → [3,5,8,1,9]. Compare 8,1 → swap → [3,5,1,8,9]. Compare 8,9 → no swap. End of pass 1: [3,5,1,8,9].

Pass 2: Compare 3,5 → no swap. Compare 5,1 → swap → [3,1,5,8,9]. Compare 5,8 → no swap. End of pass 2: [3,1,5,8,9].

Pass 3: Compare 3,1 → swap → [1,3,5,8,9]. Compare 3,5 → no swap. End of pass 3: [1,3,5,8,9].

Pass 4: No swaps are made anywhere in this pass. The list is already sorted, so the algorithm stops.

That's the level of detail a "show the stages of a bubble sort" question is actually marked on: the correct list after each pass. If your working shows the right end-of-pass states, you get full marks even if you didn't write out every individual comparison.

Linear Search vs. Bubble Sort: What's the Difference?

Linear Search

Bubble Sort

Purpose

Finds whether a target value exists in a list

Puts an entire list into order

Needs sorted data?

No (it creates the order itself)

Output

A found/not found result (and often a position)

A fully reordered list

What's compared

Each item against the target

Adjacent pairs of items against each other

Stops when

The target is found, or the list runs out

A full pass makes zero swaps

They're often taught together because they're the two simplest examples of an exam favourite: an algorithm defined as a precise, ordered set of steps that a computer follows exactly, every time, with no ambiguity.

What Mistakes Do Students Actually Make in the Exam?

Three come up constantly when marking this topic.

First, writing pseudocode that's really just Python or Java with English words swapped in. CIE pseudocode doesn't use brackets like print(), it uses OUTPUT, INPUT, IF...THEN...ENDIF. Real language syntax loses marks even when the logic is correct.

Second, describing a bubble sort by explaining every single comparison instead of the pass outcomes. It's slower to write, and it isn't what's rewarded.

Third, forgetting that a linear search's one real advantage over binary search is that it doesn't need sorted data. Students often write "it's simple" and stop there, missing the mark that's actually being tested.

If you want to drill CIE's exact pseudocode conventions until they're automatic, the Question Bank has past paper questions filtered to algorithms and pseudocode, so you're practising against the syntax examiners actually expect rather than a generic version of it.

If you want to see how these same pseudocode conventions apply once you're past algorithms and into how a program actually runs on hardware, our guide to the Fetch-Execute Cycle covers what the CPU does with the instructions your algorithm compiles down to.

Frequently Asked Questions

Is bubble sort efficient for large datasets? No. Bubble sort compares and swaps adjacent pairs repeatedly, which makes it fine for small or classroom-sized lists but slow on large ones, since every pass may only move one value fully into place. CIE doesn't require you to know formal time-complexity notation for IGCSE, but you should be able to say bubble sort gets noticeably slower as the list grows, because worst-case behaviour requires many passes over the whole list.

Does linear search need the data to be sorted first? No, and that's its main advantage over binary search. A linear search checks items in whatever order they already appear in, one at a time, so it works on unsorted lists with no extra preparation. The trade-off is that it's slower than binary search once data is sorted.

What's the difference between a "pass" and a "swap" in bubble sort? A swap is a single exchange of two adjacent values that are in the wrong order. A pass is one complete sweep through the entire list, comparing every adjacent pair once. A single pass can contain several swaps, one swap, or none at all, which is the signal to stop.

Will I be asked to fully trace a bubble sort in the CIE IGCSE exam? Yes, this is common, but you're marked on the correct list at the end of each pass, not on writing out every individual comparison. Showing [3,5,1,8,9] after pass 1, then [3,1,5,8,9] after pass 2, and so on, earns full marks if the end states are right.

Why does CIE pseudocode use OUTPUT and INPUT instead of print() and input()? Pseudocode is meant to describe the logic of an algorithm independently of any one programming language, so CIE's pseudocode conventions (OUTPUT, INPUT, DECLARE, IF...THEN...ENDIF, FOR...NEXT) are deliberately language-neutral. Writing print() or input() with brackets pulls in real Python syntax, and examiners mark that down even when the logic is entirely correct. If you're studying Edexcel International GCSE Computer Science instead of Cambridge, the same two algorithms appear under "Algorithms" in the specification, but Edexcel's own pseudocode conventions differ slightly from CIE's, so always match the exact syntax style your board's mark scheme expects.

How Should You Revise This Topic?

Don't just reread this guide. Write out both pseudocode blocks from memory, run them by hand on a five-item list you make up yourself, and check your trace against CIE's expected format: end-of-pass states for bubble sort, comparison count for linear search.

If you've written a full pseudocode answer and aren't sure whether your syntax would actually survive CIE's marking, not just whether the logic works, the AI Tutor can check it against the same conventions examiners use.