What is an algorithm?
An algorithm is a step-by-step set of instructions designed to perform a specific task or solve a particular problem. Algorithms are the foundation of all computer programs. Before writing any code, programmers plan their solution as an algorithm using either pseudocode or a flowchart. A good algorithm is unambiguous (every step is clear), finite (it eventually ends) and effective (it produces the correct output for any valid input).
Key Facts
- An algorithm must be unambiguous, finite and effective.
- Pseudocode is a structured way to write algorithms in plain English.
- Flowcharts use standard shapes: ovals (start/end), rectangles (processes), diamonds (decisions), parallelograms (input/output).
- Linear search checks every item one by one; binary search halves the list each time.
- Bubble sort compares adjacent items; merge sort divides the list and merges.
Flowcharts
A flowchart is a visual diagram that represents an algorithm using standard symbols connected by arrows. Oval shapes represent the start and end of the process. Rectangles represent processes or instructions. Diamond shapes represent decisions (yes/no questions) where the flow branches. Parallelograms represent inputs and outputs. Arrows show the direction of flow. Flowcharts are useful for visualising the logic of a program, especially when there are multiple branches or loops.
Pseudocode
Pseudocode is a way of writing algorithms using structured English that resembles programming code but is not tied to any specific language. It uses keywords like IF, THEN, ELSE, ENDIF, WHILE, ENDWHILE, FOR, NEXT, INPUT and OUTPUT. Pseudocode allows programmers to focus on the logic of the solution without worrying about syntax rules. It is easier to read than actual code and can be translated into any programming language.
Searching algorithms
Linear search
Linear search is the simplest searching algorithm. It starts at the first item in a list and checks each item one by one until it finds the target value or reaches the end of the list. It works on both sorted and unsorted data. The advantage is its simplicity, but it is slow for large datasets because in the worst case it must check every single item. For a list of n items, the worst case requires n comparisons.
Binary search
Binary search is a much faster algorithm, but it only works on data that is already sorted. It starts by looking at the middle item of the list. If this is the target, the search is complete. If the target is smaller than the middle item, the algorithm discards the upper half and repeats with the lower half. If the target is larger, it discards the lower half and repeats with the upper half. Each step halves the number of items to check, making it very efficient for large datasets.
Worked Example
Use binary search to find the number 42 in this sorted list: [3, 12, 18, 27, 33, 42, 56, 71, 89]
Step 1: The list has 9 items. The middle item (index 4) is 33. 42 is greater than 33, so discard the left half including 33.
Step 2: Remaining list: [42, 56, 71, 89]. The middle item (index 1 of this sub-list) is 56. 42 is less than 56, so discard the right half including 56.
Step 3: Remaining list: [42]. The middle item is 42. This matches the target.
Result: Found 42 in 3 comparisons. A linear search would have needed 6.
Sorting algorithms
Bubble sort
Bubble sort works by repeatedly stepping through the list, comparing each pair of adjacent items and swapping them if they are in the wrong order. After the first pass, the largest value has “bubbled” to the end of the list. The process repeats for the remaining unsorted items. The algorithm stops when a complete pass is made with no swaps, meaning the list is sorted. Bubble sort is easy to understand and implement but is inefficient for large lists because it may require many passes.
Merge sort
Merge sort uses a divide-and-conquer approach. It repeatedly divides the list into halves until each sub-list contains a single item (which is inherently sorted). It then merges pairs of sub-lists back together in the correct order, comparing the first items of each sub-list and placing the smaller one first. This continues until the entire list is reassembled in sorted order. Merge sort is much more efficient than bubble sort for large datasets, but it requires additional memory to store the sub-lists during the merge process.
Worked Example
Perform one pass of bubble sort on: [5, 3, 8, 1, 4]
Compare 5 and 3: 5 > 3, so swap. List becomes [3, 5, 8, 1, 4].
Compare 5 and 8: 5 < 8, no swap. List stays [3, 5, 8, 1, 4].
Compare 8 and 1: 8 > 1, so swap. List becomes [3, 5, 1, 8, 4].
Compare 8 and 4: 8 > 4, so swap. List becomes [3, 5, 1, 4, 8].
After one pass: [3, 5, 1, 4, 8]. The largest value (8) is now in its correct position at the end.
Practice Questions
- Explain the difference between linear search and binary search. (4 marks)
- State one advantage and one disadvantage of bubble sort. (2 marks)
- Write pseudocode for a linear search that returns the position of a target value in a list, or “Not found” if the value is not present. (4 marks)
- Explain why binary search cannot be used on an unsorted list. (2 marks)