RK

Cambridge (CIE) IGCSE Computer Science - Standard Methods of a Solution

Linear Search

  • Definition of Searching Algorithm: A precise set of instructions a computer can follow to find specific data efficiently in large datasets.
  • Linear Search:
    • Starts at the first element in a dataset and checks each value sequentially until the target value is found or all elements have been checked.
    • Key Characteristics:
    • Can be performed on unsorted datasets.

How to Perform a Linear Search:

  1. Check the first value.
  2. If it matches the target value, STOP.
  3. If not, move to the next value and check.
  4. Repeat until all values are checked or the target is found.

Example of Linear Search in Pseudocode:

DECLARE data : ARRAY[1:5] OF INTEGER
DECLARE target : INTEGER
DECLARE found : BOOLEAN

data ← [5, 2, 8, 1, 9]
target ← 11
found ← FALSE

FOR index ← 1 TO 5 DO
    IF data[index] = target THEN
        found ← TRUE
        OUTPUT "Target found"
        BREAK
    ENDIF
NEXT index

IF found = FALSE THEN
    OUTPUT "Target not found"
ENDIF

Example of Linear Search in Python:

data = [5, 2, 8, 1, 9]
target = 11
found = False

for index in range(len(data)):
    if data[index] == target:
        found = True
        print("Target found")
        break

if not found:
    print("Target not found")

Bubble Sort

  • Definition of Sorting Algorithm: A systematic procedure for arranging elements in a specific order (ascending or descending) in data.
  • Bubble Sort:
    • A simple sorting algorithm that repeatedly steps through the list, compares adjacent pairs, and swaps them if they are in the wrong order.
    • Each full pass through the list is called a pass. The algorithm finishes when no swaps are needed in a complete pass.

How to Perform a Bubble Sort:

  1. Compare the first two values.
  2. If they are in the wrong order, swap them.
  3. Move to the next pair and repeat step 2.
  4. Continue until the end of the dataset (completing pass 1).
  5. If swaps were made during the last pass, repeat from step 1 (next pass).
  6. If no swaps were made, stop; the list is sorted.

Example of Bubble Sort:

Dataset: [5, 2, 4, 1, 6, 3]

Step-by-Step:
  1. Compare 5 and 2: Swap → [2, 5, 4, 1, 6, 3]
  2. Compare 5 and 4: Swap → [2, 4, 5, 1, 6, 3]
  3. Compare 5 and 1: Swap → [2, 4, 1, 5, 6, 3]
  4. Compare 5 and 6: No Swap → [2, 4, 1, 5, 6, 3]
  5. Compare 6 and 3: Swap → [2, 4, 1, 5, 3, 6]
    End of Pass 1
  6. Repeat until no swaps occur.
    • Pass 2: [2, 1, 4, 3, 5, 6]
    • Pass 3: [1, 2, 3, 4, 5, 6] (No swaps; sorted.)

Pseudocode for Bubble Sort:

DECLARE nums : ARRAY[1:11] OF INTEGER
nums ← [66, 7, 69, 50, 42, 80, 71, 321, 67, 8, 39]
DECLARE numlength : INTEGER
numlength ← 11
DECLARE swaps : BOOLEAN
swaps ← TRUE

WHILE swaps DO
    swaps ← FALSE
    FOR y ← 1 TO numlength - 1 DO
        IF nums[y] > nums[y + 1] THEN
            DECLARE temp : INTEGER
            temp ← nums[y]
            nums[y] ← nums[y + 1]
            nums[y + 1] ← temp
            swaps ← TRUE
        ENDIF
    NEXT y
    numlength ← numlength - 1
ENDWHILE
OUTPUT nums

Bubble Sort in Python:

nums = [66, 7, 69, 50, 42, 80, 71, 321, 67, 8, 39]
numlength = len(nums)
swaps = True
while swaps:
    swaps = False
    for y in range(numlength - 1):
        if nums[y] > nums[y + 1]:
            nums[y], nums[y + 1] = nums[y + 1], nums[y]
            swaps = True
    numlength -= 1
print(nums)

Other Standard Methods of a Solution

Totalling & Counting

  • Totalling:
    • Keeping a cumulative sum of values.
    • Example: Calculating total for a shop receipt.
  • Counting:
    • Incrementing or decrementing a fixed value (usually by 1).
    • Often used in algorithms to track the number of iterations.

Totalling Pseudocode:

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

Counting Pseudocode:

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

Maximum, Minimum & Average

  • Purpose: To find the largest (max), smallest (min), and average values in a dataset.
  • Example: Calculating scores in a class test.

Example Pseudocode:

Total ← 0
Scores ← [25, 11, 84, 91, 27]
Highest ← max(Scores)
Lowest ← min(Scores)
FOR Count ← 0 TO LENGTH(Scores) - 1 DO
    Total ← Total + Scores[Count]
NEXT Count
Average ← Total / LENGTH(Scores)
OUTPUT "The highest score is:", Highest
OUTPUT "The lowest score is:", Lowest
OUTPUT "The average score is:", Average