Algorithms
GCSE Computer Science · AQA 3.1 Fundamentals of algorithms · OCR 2.1 Algorithms
Computational thinking
- Algorithm: a sequence of steps to solve a problem.
- Decomposition: break a problem into smaller sub-problems. Abstraction: remove unnecessary detail.
- Algorithmic thinking: identify the steps, inputs, processes and outputs.OCR only
- Represent algorithms with pseudocode or flowcharts (oval = start/end, parallelogram = input/output, rectangle = process, diamond = decision).
- Trace tables track the value of each variable as an algorithm runs – use them to find errors and outputs.
Searching algorithms
- Linear search: check each item in turn. Works on unsorted lists; slow for big lists.
- Binary search: list must be sorted. Check the middle item; discard the half that can't contain the target; repeat. Much faster for large lists.
Exam tip: Binary search on 1000 items needs at most about 10 comparisons; linear search could need 1000.
- Time efficiency: compare algorithms by how many steps they need as the input grows – binary search and merge sort scale far better than linear search and bubble sort.AQA only
Sorting algorithms
- Bubble sort: compare adjacent pairs and swap if in the wrong order; repeat passes until no swaps. Simple but slow.
- Merge sort: split the list into single items, then merge pairs back together in order. Fast for large lists but uses more memory.
- Insertion sort: take each item in turn and insert it into the correct place in the sorted part of the list.OCR only
Key terms and facts
- Algorithm
- Step-by-step instructions to solve a problem
- Decomposition
- Breaking a problem into smaller parts
- Abstraction
- Removing unnecessary detail
- Algorithmic thinking
- Working out steps to solve a problem
- Pseudocode
- Simple code-like description of an algorithm
- Flowchart: diamond shape means...
- a decision
- Flowchart: parallelogram means...
- input or output
- Linear search
- Checks each item in order
- Binary search
- Halves a sorted list each time
- Binary search needs...
- a sorted list
- Bubble sort
- Swaps neighbours until in order
- Merge sort
- Splits the list, then merges in order
- Insertion sort
- Inserts each item into the right place
- Fastest sort for big lists?
- Merge sort
- Trace table
- Tracks variable values as code runs
- Time efficiency
- How long an algorithm takes to run
Practise algorithms
← All GCSE Computer Science topics · Open GCSE Computer Science in StudySam