AS Computer Science 9618: Arrays, Linear Search and Bubble Sort

(a) A small warehouse records which slots on its storage shelving are currently occupied using a 2D array declared in pseudocode as DECLARE Shelves : ARRAY[1:8, 1:12] OF BOOLEAN, where TRUE means that slot is occupied. State the upper bound of the first index, the upper bound of the second index, and the total number of storage slots represented by this array. [3]

(b) A charity records six donation amounts, in whole pounds, received during one collection, in the array DECLARE Donations : ARRAY[1:6] OF INTEGER, containing the values 15, 42, 8, 61, 8, 27 at indices 1 to 6 respectively. A linear search is used to find the index of the first donation of exactly £8. Complete a full trace table showing each comparison made by the linear search until the target is found, and state the index at which it is found. [3]

(c) A separate array of five exam scores is declared as DECLARE Scores : ARRAY[1:5] OF INTEGER, containing the values 29, 12, 47, 8, 33 at indices 1 to 5 respectively. A bubble sort is used to sort Scores into ascending order. Complete a full trace table showing the contents of Scores after each pass of the bubble sort, including a final pass that confirms the array is sorted, and state the fully sorted array. [4]

Part (a): Bounds of a 2D array

Shelves is declared as ARRAY[1:8, 1:12] OF BOOLEAN. The first index range, 1:8, gives an upper bound of 8 for the first index (representing 8 rows of shelving). The second index range, 1:12, gives an upper bound of 12 for the second index (representing 12 slots per row). The total number of storage slots is the product of the two dimensions:

8 × 12 = 96 slots.

[3 marks]: [1] for upper bound of first index = 8, [1] for upper bound of second index = 12, [1] for total slots = 96.

Part (b): Tracing a linear search

Donations holds [15, 42, 8, 61, 8, 27] at indices 1 to 6, and Target = 8. A linear search checks each element in order, starting from index 1, and stops as soon as a match is found:

DECLARE Donations : ARRAY[1:6] OF INTEGER
DECLARE Target : INTEGER
DECLARE Index : INTEGER
DECLARE Found : BOOLEAN

Target ← 8
Index ← 1
Found ← FALSE
WHILE Index <= 6 AND Found = FALSE
    IF Donations[Index] = Target
        THEN
            Found ← TRUE
        ELSE
            Index ← Index + 1
    ENDIF
ENDWHILE

Index	`Donations[Index]`	`Donations[Index] = Target`?	`Found`	Action
1	15	No	FALSE	`Index ← 2`
2	42	No	FALSE	`Index ← 3`
3	8	Yes	TRUE	loop ends

Once Found becomes TRUE at Index = 3, the WHILE loop’s condition (Found = FALSE) is no longer met, so the search stops immediately. The second donation of £8, at index 5, is never reached.

[3 marks]: [1] for correctly showing no match at indices 1 and 2, [1] for identifying the match at index 3 and stopping the search there, [1] for the final stated result, index = 3.

Part (c): Tracing a bubble sort

Scores holds [29, 12, 47, 8, 33] at indices 1 to 5. Each pass of the bubble sort compares every pair of neighbouring elements from left to right, swapping them if the left value is greater than the right value, and a pass with no swaps confirms the array is sorted:

DECLARE Scores : ARRAY[1:5] OF INTEGER
DECLARE Swapped : BOOLEAN
DECLARE Temp : INTEGER
DECLARE i : INTEGER

Swapped ← TRUE
WHILE Swapped
    Swapped ← FALSE
    FOR i ← 1 TO 4
        IF Scores[i] > Scores[i + 1]
            THEN
                Temp ← Scores[i]
                Scores[i] ← Scores[i + 1]
                Scores[i + 1] ← Temp
                Swapped ← TRUE
        ENDIF
    NEXT i
ENDWHILE

Pass 1 (starting from [29, 12, 47, 8, 33]):

Compare positions 1–2: 29 > 12, swap → [12, 29, 47, 8, 33]
Compare positions 2–3: 29 > 47? No, no swap → [12, 29, 47, 8, 33]
Compare positions 3–4: 47 > 8, swap → [12, 29, 8, 47, 33]
Compare positions 4–5: 47 > 33, swap → [12, 29, 8, 33, 47]
End of pass 1: [12, 29, 8, 33, 47] (swaps occurred)

Pass 2 (starting from [12, 29, 8, 33, 47]):

Compare positions 1–2: 12 > 29? No
Compare positions 2–3: 29 > 8, swap → [12, 8, 29, 33, 47]
Compare positions 3–4: 29 > 33? No
Compare positions 4–5: 33 > 47? No
End of pass 2: [12, 8, 29, 33, 47] (swaps occurred)

Pass 3 (starting from [12, 8, 29, 33, 47]):

Compare positions 1–2: 12 > 8, swap → [8, 12, 29, 33, 47]
Compare positions 2–3: 12 > 29? No
Compare positions 3–4: 29 > 33? No
Compare positions 4–5: 33 > 47? No
End of pass 3: [8, 12, 29, 33, 47] (swaps occurred)

Pass 4 (starting from [8, 12, 29, 33, 47]):

Compare positions 1–2: 8 > 12? No
Compare positions 2–3: 12 > 29? No
Compare positions 3–4: 29 > 33? No
Compare positions 4–5: 33 > 47? No
End of pass 4: [8, 12, 29, 33, 47]. no swaps, so the array is confirmed sorted and the algorithm stops.

[4 marks]: [1] for the correct array after pass 1, [1] for the correct array after pass 2, [1] for the correct array after pass 3, [1] for pass 4 showing no swaps and the correctly stated fully sorted array [8, 12, 29, 33, 47].

Final answers

(a) Upper bound of first index = 8; upper bound of second index = 12; total slots = 96.
(b) The first £8 donation is found at Index = 3 (comparisons at indices 1, 2 and 3 only).
(c) Pass 1: [12, 29, 8, 33, 47]; Pass 2: [12, 8, 29, 33, 47]; Pass 3: [8, 12, 29, 33, 47]; Pass 4: [8, 12, 29, 33, 47] (no swaps, sorted). Fully sorted array: [8, 12, 29, 33, 47].