The two array algorithms the AS syllabus names. A linear search checks elements one at a time until it finds the target or runs out. A bubble sort compares neighbours and swaps them, pass after pass, until the array is in order.
A linear search compares the target with each element in turn, from the first, and stops when it is found or the end of the array is reached. It works on unsorted data; in the worst case it makes n comparisons. A bubble sort compares each pair of adjacent elements and swaps them (using a temporary variable) if they are in the wrong order. After each pass the largest unsorted value has reached its final place. The improved version uses a flag to stop as soon as a pass makes no swaps and shortens each pass by one.
In the lab, search for a value that is in the list and then for one that is not. Count the comparisons each time: the second search has to check every element before it can say "not found".
DECLARE Names : ARRAY[1:8] OF STRING
DECLARE SearchName : STRING
DECLARE Index : INTEGER
DECLARE Found : BOOLEAN
INPUT SearchName
Found ← FALSE
Index ← 1
WHILE Index <= 8 AND Found = FALSE
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
Index <= 8 is FALSE and the loop stops: 8 comparisons.Ann found at position 6 after 6 comparisons; (b) Tom not found after 8 comparisonsDo not put OUTPUT "not found" inside the loop: it would be output for every element that does not match. Decide only after the loop has finished, using the Found flag.
In the lab, step through a bubble sort. Each step compares two neighbours; at the end of every pass the largest remaining value has bubbled to the end of the unsorted part.
DECLARE Nums : ARRAY[1:5] OF INTEGER
DECLARE Pass : INTEGER
DECLARE j : INTEGER
DECLARE Temp : INTEGER
FOR Pass ← 1 TO 4
FOR j ← 1 TO 4
IF Nums[j] > Nums[j + 1] THEN
Temp ← Nums[j]
Nums[j] ← Nums[j + 1]
Nums[j + 1] ← Temp
ENDIF
NEXT j
NEXT Pass
Nums[j + 1] must still be inside the array.Nums[j] ← Nums[j + 1] would overwrite the first value and lose it.Writing the swap as Nums[j] ← Nums[j + 1] then Nums[j + 1] ← Nums[j] copies one value into both elements. Always use a temporary variable.
Four quick checks. Each correct answer earns XP and records this skill on your profile.
A linear search looks for a value that is not in an array of 8 elements. How many comparisons does it make?
In the lab's bubble sort, where is the largest value at the end of the first pass?
Why does the swap in a bubble sort need a variable such as Temp?
Nums holds 6, 2, 9, 4. What does it hold after one pass of a bubble sort into ascending order?
Two improvements cut the work: stop as soon as a whole pass makes no swaps, because the array must then be sorted, and make each pass one comparison shorter, because the end of the array is already in order.
DECLARE Top : INTEGER
DECLARE Swapped : BOOLEAN
Top ← 5
REPEAT
Swapped ← FALSE
FOR j ← 1 TO Top - 1
IF Nums[j] > Nums[j + 1] THEN
Temp ← Nums[j]
Nums[j] ← Nums[j + 1]
Nums[j + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT j
Top ← Top - 1
UNTIL Swapped = FALSE OR Top = 1
Set Swapped ← FALSE at the start of every pass, inside the REPEAT. Setting it once before the loop means a single swap in pass 1 keeps it TRUE for ever.
Unlocks once the four checks above are done. Worth more XP, written to AS Paper 1 and Paper 2 standard.
A bubble sort uses IF List[j] > List[j + 1] THEN to sort into ascending order. What change sorts into descending order?
A simple bubble sort uses nested FOR loops that both run from 1 to n − 1. How many comparisons does it make for 6 elements?
What is an advantage of a linear search?
In an improved bubble sort, what is the purpose of the Boolean flag?
This skill is now recorded on your profile. Keep the chain going.