Tutorial 8

🔢

Arrays

9618 A-Level


So far we have just looked at how to store single values in variables or constants - if we need to store multiple values of the same data type, we can use arrays

Some advantages of arrays:

  • Can easily loop over them - for assigning, inputting, calculating the min/max/mean/total, searching, sorting, filtering etc
  • Less tedious and more flexible than having to create 100s of variables for our data

1

Declaration & Assignment - 1D Arrays

The general syntax for declaring an array is as follows:

DECLARE <identifier> : ARRAY[<dimensions>] OF <data type>

Note: "dimensions" should be integer pairs in the form <lower bound>:<upper bound>

Below we declare and assign to a 1D array of strings, with 5 elements - a 1D array is a simple list of elements

DECLARE names : ARRAY[1:5] OF STRING names[1] <-- "Alan" names[2] <-- "John" names[3] <-- "Grace" names[4] <-- "Donald" names[5] <-- "Tim"

Declaration & Assignment - 2D Arrays

While sometimes a 1D array is appropriate, sometimes we might want a 2D array which can be though of as a combination of rows and columns - much like a spreadsheet

For example, assume we want to store both the person's first and last name in separate, easily accessible locations - in our spreadsheet analogy, we can create a 2D array with 5 rows to store our 5 people and 2 columns to store the first & last name respectively

The other example can be used to declare a 3x3 grid for a simple board game like noughts and crosses - in this example, let's use a loop to automatically assign a space character to represent an available cell in the board grid

Note: the order you access elements is row, column, which is the opposite to e.g. x, y co-ordinates in maths - the acronym I remember being told at school to remember this was roman catholic to remember the "rc" order - an alternate acronym could be remote control

DECLARE names : ARRAY[1:5, 1:2] OF STRING DECLARE grid : ARRAY[1:3, 1:3] OF CHAR names[1, 1] <-- "Alan" names[1, 2] <-- "Turing" names[2, 1] <-- "John" names[2, 2] <-- "von Neumann" names[3, 1] <-- "Grace" names[3, 2] <-- "Hopper" names[4, 1] <-- "Donald" names[4, 2] <-- "Knuth" names[5, 1] <-- "Tim" names[5, 2] <-- "Berners-Lee" DECLARE row, col : INTEGER FOR row <-- 1 TO 3 FOR col <-- 1 TO 3 grid[row, col] <-- ' ' NEXT col NEXT row

2

Outputting Arrays - 1D

In pseudocode, you can't simply use OUTPUT arr to output the contents of an array - Cambridge want you to learn how output actually works - i.e. by looping through each element

Note: for IGCSE/O-Level, they will usually tell you the length of the array is either stored in some variable/constant - e.g. NumberOfPeople or you can infer it from the question - e.g. "hourly temperatures are taken daily" which indicates you need a 7x24 or 24x7 2D array. One question - presumably by mistake - they didn't give any way of determining the length of the array - in that case, you can just make up some variable/constant and pretend that stores the length in the 15 marker

DECLARE index : INTEGER DECLARE names : ARRAY[1:5] OF STRING names[1] <-- "Alan" names[2] <-- "John" names[3] <-- "Grace" names[4] <-- "Donald" names[5] <-- "Tim" FOR index <-- 1 TO 5 OUTPUT names[index] NEXT index

Outputting Arrays - 2D

In this case, since we only have 2 columns, we can access them directly - if we had a large number of columns, we could use a nested loop, looping through the rows in the outer loop, then the columns in the inner loop

DECLARE names : ARRAY[1:5, 1:2] OF STRING DECLARE row : INTEGER names[1, 1] <-- "Alan" names[1, 2] <-- "Turing" names[2, 1] <-- "John" names[2, 2] <-- "von Neumann" names[3, 1] <-- "Grace" names[3, 2] <-- "Hopper" names[4, 1] <-- "Donald" names[4, 2] <-- "Knuth" names[5, 1] <-- "Tim" names[5, 2] <-- "Berners-Lee" FOR row <-- 1 TO 5 OUTPUT row, ") ", names[row, 1], " ", names[row, 2] NEXT row

3

Min, Max, Sum, Mean

Many IGCSE/O-Level 15 markers and some A-Level questions require us to calculate the minimum, maximum, sum and mean of all numbers in an array

Looking at the code below, note:

  • We assign min & max as being the first element - this is since, e.g. if giving min a huge default value, then if all values happened to be larger than this, we would think the min was this default value we initially assigned it - same for max, if we chose a small/negative initial value, but the real values all happened to be less than it
  • We then loop through all elements in the array
  • Min: if the current element is smaller than the current minimum, then set this current element as the new minimum
  • Max: if the current element is bigger than the current maximum, then set this current element as the new maximum
  • Sum: add each element to the sum
  • Mean: divide the sum by the number of elements
  • Note: in this example, we could have also assigned sum to be the first element, then started our loop from element 2
DECLARE nums : ARRAY[1:5] OF INTEGER DECLARE min, max, sum, index : INTEGER DECLARE mean : REAL nums[1] <-- 6 nums[2] <-- 3 nums[3] <-- 8 nums[4] <-- 2 nums[5] <-- 5 min <-- nums[1] max <-- nums[1] FOR index <-- 1 TO 5 IF nums[index] < min THEN min <-- nums[index] ENDIF IF nums[index] > max THEN max <-- nums[index] ENDIF sum <-- sum + nums[index] NEXT index OUTPUT "Min: ", min OUTPUT "Max: ", max OUTPUT "Sum: ", sum OUTPUT "Mean: ", (sum / 5)

4

Linear Search

Often we want to search to see whether a specific value exists in an array - we can use linear search to do that:

  1. Initialise an index variable to point to first element in array
  2. Loop through array element-by-element
  3. If current element if is the value we are searching for, then update flag/return TRUE if in a function etc
  4. If item hasn't been found after looping through all elements in the array, then we know the item doesn't exist
DECLARE nums : ARRAY[1:5] OF INTEGER DECLARE targetNumber, index : INTEGER DECLARE found : BOOLEAN nums[1] <-- 6 nums[2] <-- 3 nums[3] <-- 8 nums[4] <-- 2 nums[5] <-- 5 OUTPUT "Enter number to search for:" INPUT targetNumber index <-- 1 found <-- FALSE //loop to 5, since 5 elements in array WHILE found = FALSE AND index <= 5 DO IF nums[index] = targetNumber THEN found <-- TRUE ENDIF index <-- index + 1 ENDWHILE IF found = TRUE THEN OUTPUT targetNumber, " is in the array!" ELSE OUTPUT targetNumber, " is not in the array!" ENDIF

Note: we can also write this as a function, returning TRUE if we find the item, while returning FALSE is we have looped through the entire array and not found the item

DECLARE nums : ARRAY[1:5] OF INTEGER DECLARE targetNumber : INTEGER nums[1] <-- 6 nums[2] <-- 3 nums[3] <-- 8 nums[4] <-- 2 nums[5] <-- 5 OUTPUT "Enter number to search for:" INPUT targetNumber IF LinearSearch(nums, targetNumber) = TRUE THEN OUTPUT targetNumber, " is in the array!" ELSE OUTPUT targetNumber, " is not in the array!" ENDIF FUNCTION LinearSearch(arr : ARRAY OF INTEGER, toFind : INTEGER) RETURNS BOOLEAN DECLARE index : INTEGER FOR index <-- 1 TO 5 IF arr[index] = toFind THEN RETURN TRUE ENDIF NEXT index RETURN FALSE ENDFUNCTION

5

Bubble Sort

In order to sort an array in either ascending or descending order, we can use bubble sort:

  1. Assume array is unsorted and loop to the n-1 position (e.g. 1 to 4, if 5 elements) in the array on the first iteration
  2. Compare elements pair by pair - if in the wrong order (i.e. if current element bigger than next element for ascending order...or current element smaller than next for descending order), then swap them by making use of a temporary variable
  3. If elements are not sorted after looping over all pairs, then go back to the start

More detailed comments can be seen in the code

Note: when we swap, we need the temporary variable - this is since if we do a <-- b, both variables now have the same value at this point - b <-- a will be redundant - hence why we need to move one value into a temporary variable before we update it, then assign this temporary variable value to the other variable. Drawing a picture with arrows representing the assignments between 3 variables can help with understanding.

DECLARE arrayLength : INTEGER DECLARE nums : ARRAY[1:5] OF INTEGER DECLARE targetNumber : INTEGER arrayLength <-- 5 nums[1] <-- 6 nums[2] <-- 3 nums[3] <-- 8 nums[4] <-- 2 nums[5] <-- 5 //bubble sort DECLARE temp : INTEGER DECLARE isSorted : BOOLEAN DECLARE endIndex : INTEGER endIndex <-- arrayLength - 1 //if array has 5 elements, then loop to 4, since can't compare element 5 with element 6, as there is no element 6... isSorted <-- FALSE //assume unsorted by default WHILE isSorted = FALSE DO //loop while not sorted isSorted <-- TRUE //assume is sorted, at start of each pass over all pairs - if not swaps made, then loop will terminate after this iteration FOR index <-- 1 TO endIndex //compare current with next element - if wrong order, then swap IF nums[index] > nums[index + 1] THEN //swap, using temp variable as intermediate storage temp <-- nums[index] nums[index] <-- nums[index + 1] nums[index + 1] <-- temp //since at least 1 element is not in correct order, then we need to loop again to continue sorting/check isSorted <-- FALSE ENDIF NEXT index //rightmost element sorted on 1st loop, 2nd rightmost on 2nd loop etc - hence don't need to swap these already sorted elements endIndex <-- endIndex - 1 ENDWHILE //not bubble sort - just to output FOR index <-- 1 TO arrayLength OUTPUT nums[index] NEXT index

6

Test Scores

Create a program to ask the user to enter the names (can't be empty) and test scores (validated between 0-100) of 5 students - then:

  • Count the number of students who passed (scored 50% or more)
  • Display the students in descending order of grades
  • Display the min, max, sum and total of all the marks
  • Ask the user to enter a specific student's name, then output their score, or an error message if they don't exist
DECLARE names : ARRAY[1:5] OF STRING DECLARE scores : ARRAY[1:5] OF INTEGER DECLARE index, numPassed : INTEGER numPassed <-- 0 //user input FOR index <-- 1 TO 5 OUTPUT "Enter name for student ", index INPUT names[index] WHILE names[index] = "" DO OUTPUT "Empty input - try again. Enter name for student ", index INPUT names[index] ENDWHILE OUTPUT "Enter score for ", names[index] INPUT scores[index] WHILE scores[index] < 0 OR scores[index] > 100 DO OUTPUT "Score should be within range 0-100. Enter score for ", names[index] INPUT scores[index] ENDWHILE IF scores[index] >= 50 THEN numPassed <-- numPassed + 1 ENDIF NEXT index //bubble sort DECLARE tempScore : INTEGER DECLARE tempName : STRING DECLARE isSorted : BOOLEAN DECLARE endIndex : INTEGER endIndex <-- 4 isSorted <-- FALSE WHILE isSorted = FALSE DO isSorted <-- TRUE FOR index <-- 1 TO endIndex IF scores[index] < scores[index + 1] THEN tempScore <-- scores[index] scores[index] <-- scores[index + 1] scores[index + 1] <-- tempScore tempName <-- names[index] names[index] <-- names[index + 1] names[index + 1] <-- tempName isSorted <-- FALSE ENDIF NEXT index endIndex <-- endIndex - 1 ENDWHILE OUTPUT "--- Test Results ---" FOR index <-- 1 TO 5 OUTPUT names[index], ": ", scores[index] NEXT index OUTPUT numPassed, " students passed the test" //linear search DECLARE toFind : STRING DECLARE found : BOOLEAN OUTPUT "Enter name of student's grade to find" INPUT toFind index <-- 1 found <-- FALSE WHILE index <= 5 AND found = FALSE DO IF names[index] <> toFind THEN index <-- index + 1 ELSE found <-- TRUE OUTPUT names[index], " scored ", scores[index] ENDIF ENDWHILE IF found = FALSE THEN OUTPUT "No student named ", toFind, " was found" ENDIF

7

Golf Tournament

A golf tournament consists of 4 days - each day, the player will have a score (total number of shots) - your program should

  • Ask the player to enter the scores for each of the 4 days - the score should be at least 18, symbolising the technically possible, but realistically impossible feat of achieving 18 holes in one
  • Output the lowest, highest, average daily scores, as well as their overall total score for the 4 day competition
DECLARE scores : ARRAY[1:4] OF INTEGER DECLARE dayNum, min, max, total : INTEGER DECLARE average : REAL FOR dayNum <-- 1 TO 4 OUTPUT "Enter score for day ", dayNum INPUT scores[dayNum] WHILE scores[dayNum] < 18 DO OUTPUT "Lowest possible score for 18 holes is 18 shots - try again:" INPUT scores[dayNum] ENDWHILE NEXT dayNum min <-- scores[1] max <-- scores[1] total <-- 0 FOR dayNum <-- 1 TO 4 IF scores[dayNum] < min THEN min <-- scores[dayNum] ENDIF IF scores[dayNum] > max THEN max <-- scores[dayNum] ENDIF total <-- total + scores[dayNum] NEXT dayNum average <-- total / 4 OUTPUT "Lowest Score: ", min OUTPUT "Highest Score: ", max OUTPUT "Total Score: ", total OUTPUT "Average Score: ", average