AS · Practice questions · Linear search and bubble sort

Compare, then swap.

Six original Cambridge-style questions on linear search and bubble sort, with trace tables and pseudocode mark points.

Original questions All questions on this page are original work, written in the Cambridge AS & A Level style. They are not from past papers. They test the same concepts and skills the syllabus rewards.

Keep these straight

Flags and neighbours.

Linear search: WHILE not found AND not past the end; compare, then move on; report after the loop.
Bubble sort: compare List[j] with List[j + 1]; swap with Temp if in the wrong order.
Bounds: j stops one before the last element in use, so List[j + 1] stays in range.
Improve: reset a Swapped flag every pass, stop when it stays FALSE, shorten each pass.

Explain

[3 marks]

Describe how a linear search finds a value in a 1D array.

Start at the first element (lower bound). ✓
Compare each element with the search value in turn, moving to the next if it does not match. ✓
Stop when the value is found (output its index) or when the last element has been checked (output not found). ✓

Trace

[3 marks]

Using the linear search in this lesson, Names holds Pia, Leo, Sam, Ada, Tia, Jon, Kai, Uma. State the final value of Index, the output and the number of comparisons when SearchName is (a) Jon (b) Zac.

(a) Index = 6; output Jon found at position 6; 6 comparisons. ✓
(b) Index = 9; output Zac not found. ✓
(b) 8 comparisons. ✓

Trace

[4 marks]

The improved bubble sort in this lesson is used on an array of 4 elements holding 7, 3, 9, 1 (with Top ← 4). Show the contents of the array after each pass and state how many passes are made.

After pass 1: 3, 7, 1, 9. ✓
After pass 2: 3, 1, 7, 9. ✓
After pass 3: 1, 3, 7, 9. ✓
Top becomes 1 after pass 3, so 3 passes are made. ✓

Write

[5 marks]

IDs : ARRAY[1:100] OF STRING is a global array. Write pseudocode for a function FindID(SearchID : STRING) RETURNS INTEGER that uses a linear search and returns the index of SearchID, or −1 if it is not found.

Function header and ENDFUNCTION; local Index initialised to 1 and a flag (or a result variable) initialised. ✓
Loop while Index <= 100 and the item is not found. ✓
Compare IDs[Index] = SearchID; if equal set the flag / store the index. ✓
Otherwise increment Index. ✓
RETURN Index if found, else RETURN -1. ✓

Write

[6 marks]

Names : ARRAY[1:50] OF STRING holds 50 names. Write pseudocode for an efficient bubble sort that puts the names into alphabetical order and stops as soon as the names are sorted.

Declare and initialise Top ← 50 (or a pass-length variable). ✓
Outer REPEAT ... UNTIL Swapped = FALSE OR Top = 1 (or a WHILE equivalent). ✓
Swapped ← FALSE at the start of each pass. ✓
Inner FOR j ← 1 TO Top - 1 comparing Names[j] > Names[j + 1]. ✓
Swap using a temporary STRING variable and set Swapped ← TRUE. ✓
Top ← Top - 1 after each pass. ✓

Analysis

[3 marks]

An array of 10 integers is already in ascending order. Compare the number of comparisons made by (a) a simple bubble sort with two FOR loops from 1 to 9 and (b) the improved bubble sort. Explain the difference.

(a) 9 passes × 9 comparisons = 81. ✓
(b) 9 comparisons: one pass only. ✓
No swaps are made in the first pass, so the flag stays FALSE and the improved sort stops; the simple sort always completes every pass. ✓

Mark this once you have attempted all six and checked your working. It records a Practiced badge on the topic and adds a one-time bonus. Revealing the solutions alone does not count.