array-pseudocode

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