IGCSE · Practice questions · Standard methods: linear search and bubble sort

Compare and swap.

Six original Cambridge-style questions on the linear search and bubble sort standard methods.

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

Keep these straight

Two methods, learnt by heart.

Linear search: start at item 1; compare; move on; stop when found or at the end.
Bubble sort: compare neighbours; swap if in the wrong order (using Temp).
Pass: one run through the list; the largest remaining value reaches its place.
Stop: when a whole pass makes no swaps.

Explain

[3 marks]

Describe how a linear search finds an item in an array.

Start at the first element of the array. ✓
Compare each element with the item searched for, moving to the next element each time. ✓
Stop when the item is found, or when the end of the array is reached (item not found). ✓

Trace

[3 marks]

The array Scores holds 12, 45, 7, 45, 30. A linear search for 45 stops when it finds the first match. State how many comparisons are made and the position output. Then state how many comparisons are made for a search for 8.

Searching for 45: 2 comparisons (12, then 45). ✓
Position 2 is output. ✓
Searching for 8: 5 comparisons (every element checked; not found). ✓

Trace

[3 marks]

Show the list 8, 6, 9, 2 after each pass of a bubble sort into ascending order.

After pass 1: 6, 8, 2, 9. ✓
After pass 2: 6, 2, 8, 9. ✓
After pass 3: 2, 6, 8, 9 (now in ascending order). ✓

Write

[5 marks]

The array Prices[1:10] holds real numbers. Write pseudocode for a bubble sort that puts Prices into ascending order, stopping when a pass makes no swaps.

Outer REPEAT ... UNTIL loop (or WHILE) that ends when no swap is made in a pass. ✓
Set a flag, e.g. Swap ← FALSE, at the start of each pass. ✓
Inner FOR loop from 1 TO 9 (one less than the number of items) comparing Prices[Index] > Prices[Index + 1]. ✓
Swap using a temporary variable: Temp ← Prices[Index]; Prices[Index] ← Prices[Index + 1]; Prices[Index + 1] ← Temp. ✓
Set Swap ← TRUE when a swap is made. ✓

Explain

[2 marks]

Explain why a bubble sort needs a temporary variable when it swaps two values.

When the first value is overwritten by the second, the first value is lost. ✓
Temp stores the first value so it can then be copied into the second position. ✓

Analysis

[2 marks]

A bubble sort is run on a list that is already in ascending order. Explain how many passes a sort with a swap flag makes, and why.

Only one pass is made. ✓
No pair is out of order, so no swaps are made in that pass, the flag stays FALSE and the sort stops. ✓

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.