Two standard methods appear again and again in exam algorithms. A linear search checks items one by one until it finds what it wants. A bubble sort swaps neighbouring items until the whole list is in order. Learn both well enough to write them from memory.
A linear search checks each item of a list in turn, from the first, until the item is found or the end of the list is reached. A bubble sort compares each pair of adjacent items and swaps them if they are in the wrong order. One pass moves the largest remaining item to the end. Passes repeat until a whole pass makes no swaps, so the list is sorted.
Step through the search in the lab. Each step compares one item with the target; the search stops as soon as it is found, or when every item has been checked.
DECLARE Names : ARRAY[1:6] OF STRING
DECLARE Index : INTEGER
DECLARE Found : BOOLEAN
DECLARE SearchName : STRING
// Names[1] to Names[6] hold: Ali, Bea, Chen, Dev, Eva, Finn
OUTPUT "Enter the name to find"
INPUT SearchName
Found ← FALSE
Index ← 1
WHILE Found = FALSE AND Index <= 6 DO
IF Names[Index] = SearchName
THEN
Found ← TRUE
ELSE
Index ← Index + 1
ENDIF
ENDWHILE
IF Found = TRUE
THEN
OUTPUT SearchName, " found at position ", Index
ELSE
OUTPUT SearchName, " not found"
ENDIF
Do not stop the search with only one condition. The loop needs both: stop when the item is found or when the end of the list is reached, otherwise a missing item makes Index run past the end of the array.
Watch the bubble sort in the lab. Two neighbours are compared; if the left one is bigger they swap. At the end of each pass the largest unsorted value has reached its final place.
DECLARE Values : ARRAY[1:5] OF INTEGER
DECLARE Index, Last, Temp : INTEGER
DECLARE Swap : BOOLEAN
// Values holds 7, 3, 9, 1, 5
Last ← 5
REPEAT
Swap ← FALSE
FOR Index ← 1 TO Last - 1
IF Values[Index] > Values[Index + 1]
THEN
Temp ← Values[Index]
Values[Index] ← Values[Index + 1]
Values[Index + 1] ← Temp
Swap ← TRUE
ENDIF
NEXT Index
Last ← Last - 1
UNTIL Swap = FALSE OR Last = 1
Swapping with Values[Index] ← Values[Index + 1] followed by Values[Index + 1] ← Values[Index] does not swap: both end up as the same value. Always use a temporary variable.
Four quick checks. Each correct answer earns XP and records this skill on your profile.
How does a linear search look for an item?
In a bubble sort, which items are compared?
Why does the bubble sort use the variable Temp?
In the lab, after the first pass of a bubble sort into ascending order, where is the largest value?
Exam questions often ask for the list after each pass. This table follows the algorithm above on 7, 3, 9, 1, 5. The pseudocode lab's standard methods tab runs the same kind of sort on its own data.
| Pass | Comparisons | Swaps | List after the pass |
|---|---|---|---|
| Start | 7, 3, 9, 1, 5 | ||
| 1 | 4 | 3 | 3, 7, 1, 5, 9 |
| 2 | 3 | 2 | 3, 1, 5, 7, 9 |
| 3 | 2 | 1 | 1, 3, 5, 7, 9 |
| 4 | 1 | 0 | 1, 3, 5, 7, 9 (no swaps: stop) |
The list can be sorted before the algorithm knows it. After pass 3 it is in order, but one more pass is needed to make no swaps and confirm it.
Unlocks once the four checks above are done. Worth more XP, written to IGCSE Paper 1 standard.
A list has 40 items. What is the greatest number of comparisons a linear search can make?
What is the list 5, 1, 4, 2 after ONE pass of a bubble sort into ascending order?
How does a bubble sort with a swap flag know that the list is sorted?
Which condition correctly ends a linear search loop?
This skill is now recorded on your profile. Keep the chain going.