Array Pseudocode (Cambridge (CIE) A Level Computer Science): Revision Note

Searching arrays

What is a linear search?

• A linear search starts with the first value in a dataset and checks every value one at a time until all values have been checked

• A linear search can be performed even if the values are not in order

How do you perform a linear search?

• A linear search can be used to find elements in an array

• Each element in the array is checked in order, from the lower bound to the upper bound, until the item is found or the upper bound is reached

• An example pseudocode algorithm to perform a linear search on a 1D array could be:

DECLARE List : ARRAY[0:4] OF INTEGER
DECLARE Target : INTEGER
DECLARE Found : BOOLEAN
DECLARE Index : INTEGER

// Initialise array values
List[0] ← 12
List[1] ← 25
List[2] ← 37
List[3] ← 42
List[4] ← 56

// Input the value to search for
OUTPUT "Enter the value to search for:"
INPUT Target

Found ← FALSE
Index ← 0

WHILE Index <= 4 AND Found = FALSE DO
    IF List[Index] = Target THEN
        Found ← TRUE
    ELSE
        Index ← Index + 1
    ENDIF
ENDWHILE

IF Found = TRUE THEN
    OUTPUT "Item found at index ", Index
ELSE
    OUTPUT "Item not found"
ENDIF

• Works on a fixed-size array List[0:4]

• Uses a WHILE loop for flexibility (early exit if found)

• Clearly separates input, processing, and output

Identifier table

Sorting arrays

What is a bubble sort?

• A bubble sort is a simple sorting algorithm that starts at the beginning of a dataset and checks values in 'pairs' and swaps them if they are not in the correct order

• One full run of comparisons from beginning to end is called a 'pass', a bubble sort may require multiple 'passes' to sort the dataset

• The algorithm is finished when there are no more swaps to make

How do you perform a bubble sort?

Example

• Perform a bubble sort on the following dataset

• A bubble sort can be used to put elements in an array in order

• A pseudocode algorithm for a bubble sort on a 1D array could be:

DECLARE Numbers : ARRAY[0:5] OF INTEGER
DECLARE Temp : INTEGER
DECLARE Pass : INTEGER
DECLARE Index : INTEGER
DECLARE Swapped : BOOLEAN

// Initialise the array
Numbers[0] ← 5
Numbers[1] ← 2
Numbers[2] ← 4
Numbers[3] ← 1
Numbers[4] ← 6
Numbers[5] ← 3

// Bubble sort algorithm
FOR Pass ← 1 TO 5
    Swapped ← FALSE
    FOR Index ← 0 TO 4
        IF Numbers[Index] > Numbers[Index + 1] THEN
            Temp ← Numbers[Index]
            Numbers[Index] ← Numbers[Index + 1]
            Numbers[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    IF Swapped = FALSE THEN
        // List is already sorted
        EXIT
    ENDIF
NEXT Pass

// Output the sorted array
FOR Index ← 0 TO 5
    OUTPUT Numbers[Index]
NEXT Index

• Uses a fixed array of size 6

• Includes an optimisation to exit early if no swaps were made on a pass

Identifier table