Linear Search & Bubble Sort

🎯 Syllabus & Goals 3 min

Cambridge 7.4 · Standard methods — linear search, bubble sort Paper 2 · Algorithms, Programming and Logic

By the end of this lesson you can:

1. Describe and write a linear search that uses a Found flag and reports the position.
2. Describe and write a bubble sort that stops early when a pass makes no swaps.
3. Trace both algorithms with a trace table.

Textbook: Chapter 7, §7.4.4–7.4.5 (pp. 274–276)

Recap / Warm-Up 5 min

Last lesson you met totalling, counting and max/min. The last two standard methods look for a value, and put values in order.

Quick starter

You are looking for your friend's name on an unsorted list of 200 names. What is the most names you might have to read?

🧠 Key Concept 14 min

1 · Linear search

A linear search inspects each item in a list in turn, from the first, to see if it matches the value searched for. It stops when it finds a match or reaches the end of the list. The list does not need to be sorted.

A Boolean flag, Found, starts as FALSE and becomes TRUE when a match is found. The loop stops when Found is true or the counter passes the end.

A variation keeps searching to the end to count every match — for example, how many students chose "pizza" as their favourite lunch. That uses a FOR loop and no flag.

2 · Bubble sort

A bubble sort compares each element with the next one and swaps them if they are in the wrong order, from the first element to the next-to-last. After one pass, the largest value has "bubbled" to the end and is in its final place.

Each later pass compares one fewer pair. The sort stops when a pass makes no swaps (the list is already in order) or when only one element is left to check.

Worked Example 12 min

Worked example 1 · Linear search for a name

The array StudentName[1:5] holds Ava, Leo, Mia, Kai, Zoe. Search for Kai.

OUTPUT "Please enter name to find "
INPUT Name
Found ← FALSE
Counter ← 1
REPEAT
  IF Name = StudentName[Counter]
    THEN
      Found ← TRUE
    ELSE
      Counter ← Counter + 1
  ENDIF
UNTIL Found OR Counter > ClassSize
IF Found
  THEN
    OUTPUT Name, " found at position ", Counter
  ELSE
    OUTPUT Name, " not found."
ENDIF

student_name = ["Ava", "Leo", "Mia", "Kai", "Zoe"]
name = input("Please enter name to find ")
found = False
counter = 0
while not found and counter < len(student_name):
    if name == student_name[counter]:
        found = True
    else:
        counter = counter + 1
if found:
    print(name, "found at position", counter + 1)
else:
    print(name, "not found.")

Please enter name to find Kai
Kai found at position 4

1. Set up: Found ← FALSE, Counter ← 1.the flag must start false, or the loop would stop at once.
2. Positions 1–3 miss, so Counter goes 2, 3, 4.
3. Position 4 matches: Found ← TRUE. Counter is not increased, so it still holds the position, 4.that is why the counter goes in the ELSE path.
4. Search for Sam instead: all five miss, Counter reaches 6, 6 > 5 ends the loop, and the output is Sam not found.

Worked example 2 · Bubble sort of five temperatures

Sort Temperature[1:5] = 31, 25, 38, 22, 29 into ascending order.

First ← 1
Last ← 5
REPEAT
  Swap ← FALSE
  FOR Index ← First TO Last - 1
    IF Temperature[Index] > Temperature[Index + 1]
      THEN
        Temp ← Temperature[Index]
        Temperature[Index] ← Temperature[Index + 1]
        Temperature[Index + 1] ← Temp
        Swap ← TRUE
    ENDIF
  NEXT Index
  Last ← Last - 1
UNTIL (NOT Swap) OR Last = 1

temperature = [31, 25, 38, 22, 29]
last = len(temperature) - 1
swap = True
while swap and last > 0:
    swap = False
    for index in range(last):
        if temperature[index] > temperature[index + 1]:
            temp = temperature[index]
            temperature[index] = temperature[index + 1]
            temperature[index + 1] = temp
            swap = True
    last = last - 1
print(temperature)

[22, 25, 29, 31, 38]

1. Pass 1 (Last = 5) compares 4 pairs and makes 3 swaps. 38 reaches position 5.
2. Pass 2 (Last = 4) compares 3 pairs, 2 swaps: 25, 22, 29, 31, 38. 31 is now fixed.Last ← Last - 1 skips positions already in their final place.
3. Pass 3 (Last = 3) swaps 25 and 22: 22, 25, 29, 31, 38.
4. Pass 4 (Last = 2) compares 22 and 25 — no swap. Swap stays FALSE, so NOT Swap is TRUE and the sort stops.a pass with no swaps proves the list is sorted, so more passes would waste time.

Try It Yourself 12 min

📝 Exam Practice 10 min

🗝️ Recap & Key Terms 3 min

A linear search checks each item in turn until it finds a match or reaches the end; a Boolean flag records success. A bubble sort compares neighbours and swaps them, pass after pass, until a pass makes no swaps.

Linear search

An algorithm that inspects each item in a list in turn to see if it matches the value searched for.

Bubble sort

An algorithm that makes repeated passes through a list, comparing each element with the next and swapping them if needed, until a pass makes no swaps.

Flag

A Boolean variable (TRUE/FALSE) that records whether something has happened, e.g. Found or Swap.

Pass

One run through the list from the first element to the last unsorted element.

Temporary variable

A variable (Temp) used to hold one value while two values are swapped.

Homework 1 min

Task (≤ 15 min): A list holds the favourite fruits of 25 students in Fruit[1:25]. Write pseudocode that inputs a fruit name and outputs how many students chose it. Explain why a FOR loop is used instead of REPEAT…UNTIL Found. [5]

OUTPUT "Which fruit? "
INPUT Choice
ChoiceCount ← 0
FOR Index ← 1 TO 25
  IF Fruit[Index] = Choice
    THEN
      ChoiceCount ← ChoiceCount + 1
  ENDIF
NEXT Index
OUTPUT ChoiceCount, " chose ", Choice