Refining and Optimising Algorithms

This lesson covers how to refine and optimise algorithms as required by OCR J277 Section 2.4. Refining means improving an algorithm to make it more correct, clear, or robust. Optimising means making it more efficient — faster, using less memory, or both. These are important skills for producing high-quality, robust programs.

---

What Is Refinement?

Refinement is the process of improving an algorithm or program. This might involve:

• Fixing errors discovered during testing
• Adding validation to handle unexpected inputs
• Improving clarity so the code is easier to understand
• Adding features that were missing from the initial version
• Removing redundancy — eliminating unnecessary code

Refinement is iterative — you make improvements, test them, and then make further improvements.

---

What Is Optimisation?

Optimisation is the process of making an algorithm more efficient while maintaining the same correct output. Efficiency can be measured in terms of:

Measure	Description
Time efficiency	How quickly the algorithm completes — fewer steps or comparisons
Space efficiency	How much memory the algorithm uses

OCR Exam Tip: When asked to optimise an algorithm, focus on reducing unnecessary operations. Common optimisations include: removing redundant comparisons, using better algorithms (e.g. binary search instead of linear search), and eliminating unnecessary variables or loops.

---

Example 1: Removing Redundant Code

Before refinement:

total = 0
count = 0
for i = 0 to 9
    score = int(input("Enter score: "))
    total = total + score
    count = count + 1
next i
average = total / count
print("Average: " + str(average))

After refinement:

total = 0
for i = 0 to 9
    score = int(input("Enter score: "))
    total = total + score
next i
average = total / 10
print("Average: " + str(average))

What changed: The count variable is unnecessary because the loop always runs exactly 10 times. Removing it simplifies the code without changing the output.

---

Example 2: Optimising a Search

Before optimisation — linear search that does not stop when the item is found:

names = ["Alice", "Bob", "Charlie", "Diana", "Eve"]
target = input("Enter name: ")
found = false

for i = 0 to names.length - 1
    if names[i] == target then
        found = true
        position = i
    endif
next i

if found == true then
    print("Found at index " + str(position))
else
    print("Not found")
endif

After optimisation — stops searching as soon as the item is found:

names = ["Alice", "Bob", "Charlie", "Diana", "Eve"]
target = input("Enter name: ")
found = false
i = 0

while i < names.length AND found == false
    if names[i] == target then
        found = true
        position = i
    endif
    i = i + 1
endwhile

if found == true then
    print("Found at index " + str(position))
else
    print("Not found")
endif

What changed: The for loop continues checking all elements even after finding the target. The while loop stops as soon as the item is found, saving unnecessary comparisons.

---

Example 3: Adding Validation (Refinement)

Before refinement — no input validation:

age = int(input("Enter age: "))
if age >= 18 then
    print("Adult")
else
    print("Minor")
endif

After refinement — with validation:

do
    ageInput = input("Enter age (0-150): ")
    if NOT ageInput.isNumeric() then
        print("Error: enter a number")
    elseif int(ageInput) < 0 OR int(ageInput) > 150 then
        print("Error: age must be 0-150")
    endif
until ageInput.isNumeric() AND int(ageInput) >= 0 AND int(ageInput) <= 150

age = int(ageInput)
if age >= 18 then
    print("Adult")
else
    print("Minor")
endif

---

Example 4: Optimising Bubble Sort

Before optimisation — no early termination:

for pass = 0 to n - 2
    for i = 0 to n - 2
        if list[i] > list[i + 1] then
            temp = list[i]
            list[i] = list[i + 1]
            list[i + 1] = temp
        endif
    next i
next pass

After optimisation — with swapped flag and reducing range:

n = list.length
swapped = true
while swapped == true
    swapped = false
    for i = 0 to n - 2
        if list[i] > list[i + 1] then
            temp = list[i]
            list[i] = list[i + 1]
            list[i + 1] = temp
            swapped = true
        endif
    next i
    n = n - 1
endwhile

What changed:

1. Swapped flag — stops early if a pass completes with no swaps (list is already sorted).
2. Reducing n — after each pass, the last element is in its correct position, so we check one fewer element.

---

Common Optimisation Techniques

Technique	Description	Example
Early termination	Stop a loop as soon as the result is found	Stop searching after finding the target
Avoid redundant calculations	Do not recalculate values inside loops	Calculate list.length once, not every iteration
Use better algorithms	Replace inefficient algorithms with efficient ones	Binary search instead of linear search
Remove dead code	Delete code that is never executed	Remove unreachable else branches
Simplify conditions	Combine or simplify Boolean expressions	if NOT(x > 5) → if x <= 5

---

Refinement vs Optimisation

Feature	Refinement	Optimisation
Goal	Improve correctness, robustness, clarity	Improve efficiency (speed, memory)
Examples	Fix bugs, add validation, improve names	Reduce loops, use better algorithms
When	Throughout development	After the program works correctly
Risk	Low — makes the program better	Some risk — changes may introduce bugs

flowchart LR
    A[Working prototype] --> B[Refinement]
    B --> B1[Fix logic errors]
    B --> B2[Add validation]
    B --> B3[Rename / comment / constants]
    B1 --> C[Correct + clear program]
    B2 --> C
    B3 --> C
    C --> D[Optimisation]
    D --> D1[Early termination]
    D --> D2[Remove redundancy]
    D --> D3[Better algorithm]
    D1 --> E[Efficient robust program]
    D2 --> E
    D3 --> E

---

Summary

• Refinement improves correctness, robustness, and clarity.
• Optimisation improves efficiency — fewer operations, less memory.
• Common optimisations: early termination, removing redundancy, using better algorithms.
• Always re-test after refinement or optimisation to ensure the program still works correctly.
• Optimise only after the program is correct — "make it work, then make it fast."