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?

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: 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?

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.

Pass 1 of a bubble sort on 5 1 4 2 8

Each step compares one pair of neighbours and swaps them if the left one is bigger.

  1. 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.

  2. 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.

  3. 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.

  4. 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?

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

  1. Store the list in an array. Numbers is an ARRAY[1:5] OF INTEGER holding 5, 1, 4, 2 and 8.
  2. One pass. A FOR loop with the index running over the pairs. A pair is Numbers[Index] and Numbers[Index + 1], so Index only goes up to 4: at 5, Numbers[Index + 1] would be Numbers[6], which does not exist.
  3. Swap when the left one is bigger. IF Numbers[Index] > Numbers[Index + 1].
  4. The swap needs a spare place. Copy one value into a temporary variable, Temp, first. Writing Numbers[Index] ← Numbers[Index + 1] straight away would overwrite the left value, and it would be lost for ever.
  5. 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 Pass

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?
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.

The array after each pass of the bubble sort above (separate the numbers with spaces)
PassSwaps madeArray after the pass
Start-5 1 4 2 8
13
2
3
4

    Show the completed table
    PassSwaps madeArray after the pass
    Start-5 1 4 2 8
    131 4 2 5 8
    211 2 4 5 8
    301 2 4 5 8
    401 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?

    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 = FALSE

    Swapped 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.

    Following the flag version on 5 1 4 2 8
    PassSwaps madeSwapped at the end of the passDoes the loop stop?
    13TRUENo
    2
    3

      Show the completed table
      PassSwaps madeSwapped at the end of the passDoes the loop stop?
      13TRUENo
      21TRUENo
      30FALSEYes

      The first row is given as an example. The flag version finishes after 3 passes; the first version always made 4.

      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?
      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]
      ENDIF

      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?
      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

      What is the cause, and what is the one-character change that sorts from smallest to largest?
      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?

      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: ", Checked

      For 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 as position + 1. range(len(numbers) - 1) gives the indexes 0 to 3, the four pairs of five items.
      • This program prints Tom is at position 4 and then [1, 2, 4, 5, 8]. Python has no REPEAT … UNTIL, so a while swapped: loop that starts with swapped = True does 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() and sorted()). 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

      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?
      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 Index with Index + 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.