7.4 Standard Methods of Solution - IGCSE Computer Science

Learning Objectives

By the end of this lesson, you will be able to:

Understand and explainhow a linear search works, including its advantages and disadvantages
Understand and explainhow a bubble sort works, including the concept of passes and swaps
Write CIE pseudocodefor a linear search and a bubble sort
Describethe standard methods of totalling and counting
Explain and applythe methods for finding maximum, minimum and average values in a list
Trace throughalgorithms that use these standard methods and predict their output
Applythese standard methods to solve problems in unfamiliar contexts

Key Terms

Searching algorithm

Precise step-by-step instructions that a computer can follow to efficiently locate specific data in massive datasets.

Linear search

A search that starts at the first value in a dataset and checks every value one at a time until all values have been checked. Can be performed even if values are not in order.

Sorting algorithm

Precise step-by-step instructions that a computer can follow to efficiently sort data in massive datasets.

Bubble sort

A simple sorting algorithm that starts at the beginning of a dataset and checks values in pairs, swapping them if they are not in the correct order.

Pass

One full run of comparisons from the beginning to the end of the dataset. A bubble sort may require multiple passes.

Swap

Exchanging the positions of two adjacent values in a dataset. A temporary variable is usually used to hold one value while the other is moved.

Totalling

Keeping a running total of values entered into an algorithm. The total starts at 0 and accumulates values as they are processed.

Counting

When a count is incremented or decremented by a fixed value, usually 1, each time it iterates. Counting keeps track of the number of times an action has been performed.

Maximum

The largest value in a data set, found by iterating through the list and comparing each value.

Minimum

The smallest value in a data set, found by iterating through the list and comparing each value.

Average (mean)

Calculated by summing all the values in a list and dividing by the number of values.

Boolean flag

A variable that holds either TRUE or FALSE, used to indicate whether a condition has been met (e.g. whether an item has been found or a swap has been made).

1. Linear Search

Thelinear search(or sequential search) algorithm is a simple search algorithm that starts at the left-hand side of an array (index 0) and moves through the array one item at a time. Once the item being searched for is found, the algorithm returns the index of the item in question. If the algorithm reaches the end of the array without finding the item, then it either returns an error or it returns a non-valid index depending on the implementation.

Linear search is the most basic kind of search algorithm. It involves checking each item of the list (beginning to end) until the desired item is found.

Characteristic

Linear search involves checking each element in the array one by one until the target element is found or the entire array is searched.

1.1 How a Linear Search Works

Step	Instruction
1	Check the first value
2	IF it is the value you are looking for →STOP!
3	ELSE move to the next value and check
4	REPEAT UNTIL you have checked all values and not found the value you are looking for

Example: Searching for the number 9

You have an array of numbers[3, 7, 1, 9, 5]and you want to find the number9.

Check index 0: 3 — not 9, move on
Check index 1: 7 — not 9, move on
Check index 2: 1 — not 9, move on
Check index 3:9 — found!Return index 3

Interactive: Linear Search

Watch how a linear search checks each element one at a time until it finds the target. In this example, we are searching for the value9in the array.

Target: 9

How it works:The linear search starts at index 0 and checks each value in turn. When the value matches the target, the search stops and returns the index. If the end of the array is reached without finding the target, the search returns an error.

1.2 Advantages and Disadvantages

Advantages

Doesn't require data to be in order
Works on any type of storage device
Is efficient for small data sets

Disadvantages

Is very inefficient for large data sets
May need to check every element before finding the target

1.3 CIE Pseudocode for Linear Search

FUNCTION linearSearch(items, item_to_find) RETURNS STRING
DECLARE index : INTEGER
DECLARE found : BOOLEAN
index ← 0
found ← False
WHILE (found = FALSE) AND (NOT end of data set) DO
IF items[index] = item_to_find THEN
found ← True
ELSE
index ← index + 1
ENDIF
ENDWHILE
IF found = True THEN
RETURN "Item found at position ", index
ELSE
RETURN "Item not found"
ENDIF
ENDFUNCTION

Understanding the pseudocode

We declare two local variables:index(to track our position) andfound(a Boolean flag).
We setindex ← 0(starting at the beginning) andfound ← False(we haven't found it yet).
The WHILE loop continues as long as we haven't found the item AND we haven't reached the end of the data set.
Inside the loop, we check if the current item matches the target. If it does, we setfound ← True. If not, we move to the next item (index ← index + 1).
After the loop, we check the found flag. If it is true, we return the position; otherwise, we return "Item not found".

1.4 Python Code for Linear Search

# Identify the dataset to search, the target value and set the initial flag
data = [5, 2, 8, 1, 9]
target = 11
found = False
# Loop through each element in the data
for index in range(0, len(data)):
if data[index] == target:
found = True
print("Target found")
break # Exit the loop if the target is found
# If the target is not found, output a message
if not found:
print("Target not found")

Real-Life Example: Finding a Student's Name

A teacher has a list of student names and wants to check whether a particular student is in the class. A linear search would check each name in the list one by one until it finds the student's name (or reaches the end of the list).

Activity 1: Trace a Linear Search

Consider the array:[12, 45, 7, 23, 56, 89, 34]. You are searching for the value56.

List the values that are checked before 56 is found.
How many comparisons are made in total?
What is returned if the search is for the value 99?

Solution:

Values checked:12, 45, 7, 23 — 56 is the 5th element (index 4).
Total comparisons:5 comparisons (12, 45, 7, 23, 56).
Search for 99:All 7 elements are checked (12, 45, 7, 23, 56, 89, 34), then "Item not found" or -1 is returned.

Check Your Understanding: Linear Search

1. Describe how a linear search works. [3 marks]

Answer

[1 mark]Starts at the first value in a dataset
[1 mark]Checks every value one at a time until the target is found or all values have been checked
[1 mark]Does not require the data to be in order

2. State two advantages and two disadvantages of a linear search. [4 marks]

Answer

Advantages (any 2):

Doesn't require data to be in order
Works on any type of storage device
Is efficient for small data sets

Disadvantages (any 2):

Is very inefficient for large data sets
May need to check every element before finding the target

3. Write CIE pseudocode for a linear search that searches an array callednumbersfor a target valuetarget. [5 marks]

Answer

DECLARE index : INTEGER
DECLARE found : BOOLEAN
index ← 0
found ← FALSE
WHILE index < LENGTH(numbers) AND found = FALSE DO
IF numbers[index] = target THEN
found ← TRUE
ELSE
index ← index + 1
ENDIF
ENDWHILE
IF found = TRUE THEN
OUTPUT "Target found at index ", index
ELSE
OUTPUT "Target not found"
ENDIF

Marking:Correct variable declarations (1), WHILE loop with correct condition (1), IF check inside loop (1), increment index (1), output found/not found (1).

4. Explain why a linear search might return -1 when the item is not found. [2 marks]

Answer

[1 mark]-1 is not a valid index in a zero-based array (indices start at 0)
[1 mark]So returning -1 indicates that the item was not found, since no valid position could be returned

5. Why is a linear search described as "very inefficient for large data sets"? [2 marks]

Answer

[1 mark]In the worst case (item not in the list or at the end), every single element must be checked
[1 mark]As the data set grows larger, the number of comparisons grows proportionally, making it slow for large data sets

6. A linear search is performed on the array[10, 25, 30, 45, 50]searching for 30. How many comparisons are made? [1 mark]

Answer

[1 mark]3 comparisons (10, 25, 30) — the search stops once 30 is found at index 2.

2. Bubble Sort

Abubble sortis a simple sorting algorithm that starts at the beginning of a dataset and checks values inpairs, swapping them if they are not in the correct order. One full run of comparisons from beginning to end is called apass; a bubble sort may require multiple passes to sort the dataset. The algorithm is finished when there are no more swaps to make.

How bubble sort works

Sorts an unordered list of items
Compares each item with the next and swaps them if they are out of order — in effect, bubbling the largest (or smallest) item up to the end of the list
Finishes when no more swaps need to be made
The most inefficient of the sorting algorithms but very easy to implement
A popular choice for very small data sets

2.1 How a Bubble Sort Works — Step by Step

Step	Instruction
1	Compare the first two values in the dataset
2	IF they are in the wrong order… →Swap them
3	Compare the next two values
4	REPEAT step 2 & 3 until you reach the end of the dataset (pass 1)
5	IF you have made any swaps… →REPEATfrom the start (pass 2, 3, 4…)
6	ELSE you have not made any swaps… →STOP!the list is in the correct order

Worked Example: Sorting[5, 2, 4, 1, 6, 3]

PASS 1:5 & 2 — 5 > 2 →SWAP→ [2, 5, 4, 1, 6, 3]

PASS 1:5 & 4 — 5 > 4 →SWAP→ [2, 4, 5, 1, 6, 3]

PASS 1:5 & 1 — 5 > 1 →SWAP→ [2, 4, 1, 5, 6, 3]

PASS 1:5 & 6 — 5 < 6 →NO SWAP→ [2, 4, 1, 5, 6, 3]

PASS 1:6 & 3 — 6 > 3 →SWAP→ [2, 4, 1, 5, 3, 6]

End of pass 1:[2, 4, 1, 5, 3, 6] — the largest value (6) is now at the end

PASS 2:2 & 4 — 2 < 4 →NO SWAP→ [2, 4, 1, 5, 3, 6]

PASS 2:4 & 1 — 4 > 1 →SWAP→ [2, 1, 4, 5, 3, 6]

PASS 2:4 & 5 — 4 < 5 →NO SWAP→ [2, 1, 4, 5, 3, 6]

PASS 2:5 & 3 — 5 > 3 →SWAP→ [2, 1, 4, 3, 5, 6]

End of pass 2:[2, 1, 4, 3, 5, 6]

PASS 3:2 & 1 — 2 > 1 →SWAP→ [1, 2, 4, 3, 5, 6]

PASS 3:2 & 4 — 2 < 4 →NO SWAP→ [1, 2, 4, 3, 5, 6]

PASS 3:4 & 3 — 4 > 3 →SWAP→ [1, 2, 3, 4, 5, 6]

End of pass 3:[1, 2, 3, 4, 5, 6]

PASS 4:No swaps made →STOP! The list is sorted.

Examiner Tips and Tricks

In the exam youdo not have to show every swapthat takes place in a bubble sort. You can show the outcome of a bubble sort at the end of each pass. If you have the outcome of each pass correct then a bubble sort has been implemented correctly and all marks will be given!

Interactive: Bubble Sort

Watch how a bubble sort works by stepping through each comparison and swap. The array starts unsorted:[5, 2, 4, 1, 6, 3].

Pass 0 — Ready to start

How it works:The bubble sort compares adjacent pairs and swaps them if they are in the wrong order. After each full pass, the largest remaining value has "bubbled" to the end of the list. The algorithm stops when a pass makes no swaps — meaning the list is sorted.

2.2 CIE Pseudocode for Bubble Sort

FUNCTION bubbleSort(items)
DECLARE n : INTEGER
DECLARE swapped : BOOLEAN
n ← items.Length
swapped ← True
WHILE n > 0 AND swapped DO
swapped ← False
n ← n - 1
FOR index ← 0 TO n - 1
IF items[index] > items[index+1] THEN
Swap(items[index], items[index+1])
swapped ← True
ENDIF
NEXT index
ENDWHILE
RETURN items
ENDFUNCTION

Understanding the pseudocode

We declaren(to track how far through the array we need to travel) andswapped(a Boolean flag).
We setn ← items.Lengthandswapped ← True.
The WHILE loop continues as long asn > 0 AND swappedis true.
Inside the loop, we setswapped ← Falseand decrementnby 1.
The FOR loop runs from 0 to n-1, comparing each adjacent pair.
If items[index] > items[index+1], we swap them and setswapped ← True.
When the WHILE loop exits, the array is sorted and we return it.

Alternative Swap Without a Made-Up Function

temp ← items[index]
items[index] ← items[index + 1]
items[index + 1] ← temp

2.3 Python Code for Bubble Sort

# Unsorted dataset
num = [66, 7, 69, 50, 42, 80, 71, 321, 67, 8, 39]
# Count the length of the dataset
numlength = len(num)
# Set a flag to initiate the loop
swaps = True
while swaps:
swaps = False
for y in range(numlength - 1):
if num[y] > num[y + 1]:
num[y], num[y + 1] = num[y + 1], num[y]
swaps = True
numlength = numlength - 1
# Print the sorted list
print(num)

Real-Life Example: Sorting Student Names

A teacher has a list of student names and wants them in alphabetical order. A bubble sort would compare adjacent names and swap them if they are in the wrong order (e.g. "Zara" before "Adam" would be swapped). After several passes, the list would be fully sorted.

Activity 2: Trace a Bubble Sort

Perform a bubble sort on the dataset:[9, 2, 4, 7, 10, 3, 1]

Show the state of the list at the end of pass 1.
Show the state of the list at the end of pass 2.
How many passes are needed to fully sort the list?

Solution:

End of pass 1:[2, 4, 7, 9, 3, 1, 10] — 10 has bubbled to the end.
End of pass 2:[2, 4, 7, 3, 1, 9, 10] — 9 has bubbled to its correct position.
Number of passes:5 passes are needed (after pass 5, no swaps are made, so the list is sorted).

Check Your Understanding: Bubble Sort

1. Describe how a bubble sort works. [3 marks]

Answer

[1 mark]Starts at the beginning of a dataset and checks values in pairs
[1 mark]Swaps them if they are not in the correct order
[1 mark]Repeats (multiple passes) until no more swaps are needed

2. What is a "pass" in a bubble sort? [1 mark]

Answer

[1 mark]One full run of comparisons from the beginning to the end of the dataset

3. State two characteristics of a bubble sort. [2 marks]

Answer

[1 mark]It is the most inefficient of the sorting algorithms but very easy to implement
[1 mark]It is a popular choice for very small data sets
[Additional]It finishes when no more swaps need to be made

4. Write CIE pseudocode for a bubble sort. [6 marks]

Answer

DECLARE n : INTEGER
DECLARE swapped : BOOLEAN
DECLARE temp : INTEGER
n ← items.Length
swapped ← True
WHILE n > 0 AND swapped DO
swapped ← False
n ← n - 1
FOR index ← 0 TO n - 1
IF items[index] > items[index+1] THEN
temp ← items[index]
items[index] ← items[index+1]
items[index+1] ← temp
swapped ← True
ENDIF
NEXT index
ENDWHILE

Marking:Correct variable declarations (1), WHILE loop with correct condition (1), FOR loop for comparisons (1), correct IF condition (1), correct swap using temp variable (1), set swapped to True (1).

5. After one pass of a bubble sort on[8, 3, 6, 1, 9, 2], what is the state of the list? [2 marks]

Answer

[2 marks][3, 6, 1, 8, 2, 9] — the largest value (9) has bubbled to the end of the list.

6. Explain why a bubble sort is described as "inefficient". [2 marks]

Answer

[1 mark]It makes many comparisons and swaps, even when the list is almost sorted
[1 mark]For large data sets, it takes a long time to run compared to more efficient sorting algorithms

3. Totalling

Totallingrefers to maintaining a total that values are added to. There are many situations where you might want to use totalling in your programs — for example, keeping a running total of marks awarded to a student during a test.

Key idea

It is good practice to alwaysinitialise variables, so we start by setting the total to zero. Then we add each value to the total as we process it.

3.1 CIE Pseudocode for Totalling

Total ← 0
FOR Counter ← 1 TO ReceiptLength
INPUT ItemValue
Total ← Total + ItemValue
NEXT Counter
OUTPUT Total

This line is performing totalling by adding together the marks held in an array calledStudentsTest:

Total ← 0
FOR Counter ← 1 TO MaxNoOfQuestionsInTest
Total ← Total + StudentsTest[Counter]
NEXT Counter

3.2 Python Code for Totalling

def total(numbers):
return sum(numbers)
# Example usage
numbers = [1, 2, 3, 4, 5]
total_sum = total(numbers)
print("Total sum:", total_sum)

Total sum: 15

Real-Life Example: Shop Receipt

When you buy items at a shop, the till keeps a running total. Each time an item is scanned, its price is added to the total. At the end, the total is displayed on the receipt. This is exactly how totalling works in an algorithm.

Activity 3: Totalling Practice

Write CIE pseudocode for a program that asks the user for the prices of 10 items and outputs the total cost.

Solution:

DECLARE Total : REAL
DECLARE Price : REAL
DECLARE Count : INTEGER
Total ← 0
FOR Count ← 1 TO 10
OUTPUT "Enter the price of item ", Count
INPUT Price
Total ← Total + Price
NEXT Count
OUTPUT "The total cost is: ", Total

Check Your Understanding: Totalling

1. Define "totalling" in the context of algorithms. [2 marks]

Answer

[1 mark]Totalling is maintaining a running total that values are added to
[1 mark]It is used to sum up all the values in a list

2. Why is it good practice to initialise the total to 0 before adding values? [2 marks]

Answer

[1 mark]If the total is not initialised, it may contain an unpredictable value, leading to an incorrect result
[1 mark]Initialising to 0 ensures the total starts from a clean state and correctly accumulates the values

3. Write CIE pseudocode to total the values in an array calledmarksthat has 20 elements. [4 marks]

Answer

DECLARE Total : INTEGER
DECLARE Count : INTEGER
Total ← 0
FOR Count ← 1 TO 20
Total ← Total + marks[Count]
NEXT Count
OUTPUT "The total is: ", Total

Marking:Correct variable declarations (1), Total initialised to 0 (1), correct FOR loop (1), correct addition (1).

4. A program totals the values in an array[15, 27, 8, 42, 33]. What is the final total? [1 mark]

Answer

[1 mark]15 + 27 + 8 + 42 + 33 = 125

4. Counting

Countingis when a count is incremented or decremented by a fixed value, usually 1, each time it iterates. Counting keeps track of the number of times an action has been performed. Many algorithms use counting, including the linear search to track which element is currently being considered.

4.1 Counting Up and Counting Down

Counting Up (incrementing)

Keeping count of the number of times a particular action is performed — for example, counting up the number of students that have been awarded a pass mark in a test.

PassCount ← 0
FOR Counter ← 1 TO ClassSize
INPUT StudentMark
IF StudentMark > 50 THEN
PassCount ← PassCount + 1
ENDIF
NEXT Counter

Counting Down (decrementing)

A retailer keeping track of how much stock they have left so they know when to put in an order.

...
StockAvailable ← StockAvailable - 1
IF StockAvailable < 10 THEN
CALL OrderNewStock()
...

4.2 CIE Pseudocode for Counting

Count ← 0
DO
OUTPUT "Pass number", Count
Count ← Count + 1
UNTIL Count >= 50

4.3 Python Code for Counting

def count_elements(arr, target):
return arr.count(target)
# Example usage
numbers = [1, 2, 3, 4, 2, 5, 2]
target = 2
count = count_elements(numbers, target)
print(f"Count of {target}: {count}")

Count of 2: 3

Real-Life Example: Counting Passes

A teacher marks a test for 30 students. As each mark is entered, the teacher checks whether it is 50 or more. If it is, the pass count is increased by 1. At the end, the teacher knows how many students passed. This is counting up. If the teacher starts with 30 students and subtracts 1 each time a student is absent, that's counting down.

Activity 4: Counting Practice

A program counts how many numbers in an array are negative. Write CIE pseudocode for this.

Array:[-3, 5, -1, 7, -8, 2, -4]

Solution:

DECLARE NegativeCount : INTEGER
DECLARE Count : INTEGER
DECLARE numbers : ARRAY [1:7] OF INTEGER
numbers ← [-3, 5, -1, 7, -8, 2, -4]
NegativeCount ← 0
FOR Count ← 1 TO 7
IF numbers[Count] < 0 THEN
NegativeCount ← NegativeCount + 1
ENDIF
NEXT Count
OUTPUT "Number of negative values: ", NegativeCount

The output would be:4(the values -3, -1, -8, -4).

Check Your Understanding: Counting

1. Define "counting" in the context of algorithms. [2 marks]

Answer

[1 mark]Counting is when a count is incremented or decremented by a fixed value, usually 1
[1 mark]It keeps track of the number of times an action has been performed

2. Give one example of counting up and one example of counting down. [2 marks]

Answer

[1 mark]Counting up: counting how many students passed a test
[1 mark]Counting down: a retailer keeping track of remaining stock

3. Write CIE pseudocode to count how many times the value 5 appears in an array callednumbers. [4 marks]

Answer

DECLARE FiveCount : INTEGER
DECLARE Count : INTEGER
FiveCount ← 0
FOR Count ← 1 TO LENGTH(numbers)
IF numbers[Count] = 5 THEN
FiveCount ← FiveCount + 1
ENDIF
NEXT Count
OUTPUT "Number of 5s: ", FiveCount

Marking:FiveCount initialised to 0 (1), FOR loop (1), correct IF check (1), correct increment (1).

4. How is counting used in a linear search? [2 marks]

Answer

[1 mark]Theindexvariable counts through the array positions
[1 mark]It is incremented each time the search moves to the next element, keeping track of which position is currently being checked

5. Finding Maximum, Minimum and Average Values

Being able to find thelargestandsmallestvalues in a data set is another common technique used in algorithms — for example, finding the highest and lowest marks awarded to students in a class. Following on from the totalling method we looked at earlier, it is also very common to calculate theaverage(mean) of a set of values.

5.1 CIE Pseudocode for Maximum and Minimum

MaximumMark ← 0
MinimumMark ← 100
FOR Counter ← 1 TO ClassSize
IF StudentMark[Counter] > MaximumMark THEN
MaximumMark ← StudentMark[Counter]
ENDIF
IF StudentMark[Counter] < MinimumMark THEN
MinimumMark ← StudentMark[Counter]
ENDIF
NEXT Counter

Initialisation tip

Initialise the maximum to thelowest possible mark(e.g. 0) and the minimum to thehighest possible mark(e.g. 100). This ensures that the first actual mark will always be higher than the maximum and lower than the minimum.

5.2 CIE Pseudocode for Average

Total ← 0
FOR Counter ← 1 TO MaxNoOfQuestionsInTest
Total ← Total + StudentsTest[Counter]
NEXT Counter
Average ← Total / MaxNoOfQuestionsInTest

Here we calculate the average from the total after the loop has completed.

5.3 Python Code for Maximum, Minimum and Average

def find_maximum(arr):
return max(arr)
def find_minimum(arr):
return min(arr)
def find_average(arr):
return sum(arr) / len(arr)
# Example usage
numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
max_value = find_maximum(numbers)
min_value = find_minimum(numbers)
average_value = find_average(numbers)
print("Maximum value:", max_value)
print("Minimum value:", min_value)
print("Average value:", average_value)

Maximum value: 9
Minimum value: 1
Average value: 4.0

Real-Life Example: Test Scores

In a list of student test scores:[25, 11, 84, 91, 27]

Highest:91 (maximum)
Lowest:11 (minimum)
Total:25 + 11 + 84 + 91 + 27 = 238
Average:238 ÷ 5 = 47.6

Activity 5: Max, Min and Average

Consider the array of temperatures:[18, 22, 15, 30, 25, 19, 28].

What is the maximum temperature?
What is the minimum temperature?
What is the average temperature?
Write CIE pseudocode to find the maximum temperature.

Solution:

Maximum:30
Minimum:15
Average:(18 + 22 + 15 + 30 + 25 + 19 + 28) ÷ 7 = 157 ÷ 7 = 22.43
Pseudocode for maximum:
DECLARE MaxTemp : INTEGER
DECLARE Count : INTEGER
MaxTemp ← 0
FOR Count ← 1 TO 7
IF temperatures[Count] > MaxTemp THEN
MaxTemp ← temperatures[Count]
ENDIF
NEXT Count
OUTPUT "Maximum temperature: ", MaxTemp

Check Your Understanding: Max, Min and Average

1. Describe how to find the maximum value in a list. [3 marks]

Answer

[1 mark]Initialise the maximum to the lowest possible value
[1 mark]Iterate through the list, comparing each value with the current maximum
[1 mark]If a value is greater than the current maximum, update the maximum to that value

2. Explain how the average of a set of values is calculated. [2 marks]

Answer

[1 mark]Sum all the values in the list to find the total
[1 mark]Divide the total by the number of values in the list

3. Write CIE pseudocode to find both the maximum and minimum values in an array callednumbers. [5 marks]

Answer

DECLARE Maximum : INTEGER
DECLARE Minimum : INTEGER
DECLARE Count : INTEGER
Maximum ← 0
Minimum ← 1000
FOR Count ← 1 TO LENGTH(numbers)
IF numbers[Count] > Maximum THEN
Maximum ← numbers[Count]
ENDIF
IF numbers[Count] < Minimum THEN
Minimum ← numbers[Count]
ENDIF
NEXT Count
OUTPUT "Maximum: ", Maximum
OUTPUT "Minimum: ", Minimum

Marking:Correct initialisations (1), FOR loop (1), maximum comparison (1), minimum comparison (1), correct outputs (1).

4. An array contains the values[45, 12, 78, 33, 91, 22, 67]. Find the maximum, minimum and average. [3 marks]

Answer

[1 mark]Maximum:91
[1 mark]Minimum:12
[1 mark]Average:(45 + 12 + 78 + 33 + 91 + 22 + 67) ÷ 7 = 348 ÷ 7 = 49.71

Key Takeaways

Alinear searchchecks each element one by one until the target is found or the end is reached. It does not require data to be in order but is inefficient for large data sets.
Abubble sortcompares adjacent pairs and swaps them if they are out of order. It finishes when no more swaps are made.
Apassis one full run of comparisons from beginning to end. A bubble sort may require multiple passes.
Both linear search and bubble sort can be written inCIE pseudocodeusing a Boolean flag (foundorswapped) to control the loops.
Totallingmeans keeping a running total. Initialise the total to 0 and add each value as it is processed.
Countingmeans incrementing or decrementing a count by a fixed value (usually 1) each time an action is performed.
To find themaximum, initialise to the lowest possible value and update when a higher value is found.
To find theminimum, initialise to the highest possible value and update when a lower value is found.
Theaverageis calculated by totalling all values and dividing by the number of values.
These standard methods form the building blocks for solving more complex algorithm problems.

Question Bank

1. Explain how a linear search works and state one advantage and one disadvantage of using it. [5 marks]

Answer

[2 marks]Starts at the first value and checks every value one at a time until the target is found or all values have been checked
[1 mark]Does not require the data to be in order
[1 mark]Advantage:Works on any storage device / efficient for small data sets / simple to implement
[1 mark]Disadvantage:Very inefficient for large data sets / may need to check every element

2. Describe the steps involved in a bubble sort. [4 marks]

Answer

[1 mark]Compare the first two values in the dataset
[1 mark]If they are in the wrong order, swap them
[1 mark]Compare the next two values and repeat until the end of the dataset (pass 1)
[1 mark]If any swaps were made, repeat from the start; stop when no swaps are made

3. Write CIE pseudocode for a linear search. [5 marks]

Answer

DECLARE index : INTEGER
DECLARE found : BOOLEAN
index ← 0
found ← FALSE
WHILE index < LENGTH(items) AND found = FALSE DO
IF items[index] = target THEN
found ← TRUE
ELSE
index ← index + 1
ENDIF
ENDWHILE
IF found = TRUE THEN
OUTPUT "Item found at position ", index
ELSE
OUTPUT "Item not found"
ENDIF

Marking:Correct variable declarations (1), correct WHILE loop (1), IF check (1), increment index (1), correct output (1).

4. Write CIE pseudocode for a bubble sort. [6 marks]

Answer

DECLARE n : INTEGER
DECLARE swapped : BOOLEAN
DECLARE temp : INTEGER
n ← items.Length
swapped ← True
WHILE n > 0 AND swapped DO
swapped ← False
n ← n - 1
FOR index ← 0 TO n - 1
IF items[index] > items[index+1] THEN
temp ← items[index]
items[index] ← items[index+1]
items[index+1] ← temp
swapped ← True
ENDIF
NEXT index
ENDWHILE
RETURN items

Marking:Correct declarations (1), WHILE loop with correct condition (1), FOR loop (1), correct IF condition (1), correct swap using temp (1), set swapped to True (1).

5. Explain the difference between totalling and counting. Give an example of each. [4 marks]

Answer

[1 mark]Totalling:keeping a running total that values are added to
[1 mark]Example:adding up the prices of items in a shopping basket to get the total cost
[1 mark]Counting:incrementing or decrementing a count by a fixed value (usually 1) each time an action is performed
[1 mark]Example:counting how many students scored above 50 in a test

6. Write CIE pseudocode to find the maximum, minimum and average values in an array of 10 numbers. [6 marks]

Answer

DECLARE numbers : ARRAY [1:10] OF INTEGER
DECLARE Max : INTEGER
DECLARE Min : INTEGER
DECLARE Total : INTEGER
DECLARE Average : REAL
DECLARE Count : INTEGER
Max ← 0
Min ← 1000
Total ← 0
FOR Count ← 1 TO 10
IF numbers[Count] > Max THEN
Max ← numbers[Count]
ENDIF
IF numbers[Count] < Min THEN
Min ← numbers[Count]
ENDIF
Total ← Total + numbers[Count]
NEXT Count
Average ← Total / 10
OUTPUT "Maximum: ", Max
OUTPUT "Minimum: ", Min
OUTPUT "Average: ", Average

Marking:Correct initialisations (1), FOR loop (1), max logic (1), min logic (1), totalling (1), average calculation and outputs (1).

7. Perform a bubble sort on the dataset[9, 2, 4, 7, 10, 3, 1]. Show the state of the list at the end of pass 1 and pass 2. [4 marks]

Answer

[2 marks]End of pass 1:[2, 4, 7, 9, 3, 1, 10]
[2 marks]End of pass 2:[2, 4, 7, 3, 1, 9, 10]
[Additional]After pass 3: [2, 4, 3, 1, 7, 9, 10]; after pass 4: [2, 3, 1, 4, 7, 9, 10]; after pass 5: [2, 1, 3, 4, 7, 9, 10]; after pass 6: [1, 2, 3, 4, 7, 9, 10] — sorted

8. Explain why it is important to initialise variables (such as total, maximum and minimum) before using them in a loop. [3 marks]

Answer

[1 mark]If a variable is not initialised, it may contain an unpredictable value left over from previous use
[1 mark]This would cause the algorithm to produce incorrect results (e.g. a total might start at a random number instead of 0)
[1 mark]Initialising to an appropriate starting value ensures the algorithm behaves correctly and consistently every time