Exam Board:
OCR A-Level
Specification:
Computer Science H446
3.1f - Standard Algorithms
Watch on YouTube:
Bubble sort
Merge sort
Insertion sort
Quick sort
Linear search
Binary search
Djisktra's algorithm
A* algorithm
The OCR A-Level course requires an understanding of algorithms used for sorting, searching and pathfinding including how they can be used for traversing and how to write them in pseudocode or a high-level programming langauge.
Bubble Sort
Bubble sort repeatedly compares adjacent items and swaps them if they are in the wrong order.
Its advantage is that it is very simple to understand and easy to implement.
However, it is extremely slow for large lists, with a worst- and average-case time complexity of O(n²). It performs slightly better (O(n)) if the list is already nearly sorted and the algorithm is optimised to detect no swaps. Overall, it is easy but inefficient.
Merge Sort
Merge sort is a divide-and-conquer algorithm that repeatedly splits a list into smaller sublists, sorts them recursively and then merges them back together.
Its major benefit is that it is consistently fast with a time complexity of O(n log n) in the best, average and worst cases, making it very efficient for large datasets. It is also stable and works well with linked lists.
However, a drawback is that it requires additional memory to store the temporary sublists, making its space complexity O(n). Merge sort is therefore reliable but not memory-efficient.
Insertion Sort
Insertion sort works by taking each item and inserting it into the correct position in a growing sorted portion of the list.
It is efficient for small or nearly sorted datasets and has a best-case complexity of O(n), making it useful in real-time systems or hybrid algorithms.
However, for large, randomly ordered datasets it becomes slow, with average- and worst-case performance of O(n²). It uses very little memory space - (O(1) - which is one of its key benefits compared to more complex sorts like merge or quick.
Quick Sort
Quick sort is a divide-and-conquer algorithm that chooses a pivot, partitions the list into smaller elements and larger elements, and recursively sorts the partitions.
Its main advantage is speed: the average-case time complexity is O(n log n) and it is often faster in practice than merge sort due to good cache performance and in-place partitioning.
However, if poor pivot choices are made (e.g., always picking the first item in an already sorted list), the worst case becomes O(n²). Despite this, quick sort is widely used because good pivot-selection strategies minimise this risk.
Linear Search
Linear search checks each item in a list one by one until it finds the target value or reaches the end.
Its benefit is that it works on any list (sorted or unsorted) and is extremely simple to use and implement.
The drawback is inefficiency for large datasets because its best, average and worst time complexity is O(n). This means the time taken grows directly with the size of the list, making it suitable only for small collections of data.
Binary Search
Binary search repeatedly halves a sorted list to locate a target value, making it much faster than linear search.
Its key benefit is efficiency: the time complexity is O(log n) for best, average and worst cases, meaning performance scales extremely well with large datasets.
However, its major limitation is that the data must be sorted beforehand, and maintaining a sorted list can itself be costly. When this condition is met, binary search is one of the most efficient searching algorithms available.
Dijkstra's Algorithm
Dijkstra’s algorithm is a pathfinding algorithm used to find the shortest path from a starting node to all other nodes in a weighted graph with non-negative edge weights.
It works by gradually exploring the graph, always choosing the next closest unvisited node, updating the shortest known distances to its neighbours and marking nodes as 'visited' once the shortest path to them is confirmed.
The algorithm continues until all nodes have been processed or the destination is reached, guaranteeing the shortest path.
A* Algorithm
The A* algorithm is an informed pathfinding algorithm that also finds the shortest path in a weighted graph, but it uses a heuristic (an estimate of the distance to the goal) to guide its search more efficiently toward the target.
A* combines the actual cost from the start to a node with a heuristic estimate of the remaining distance, allowing it to prioritise exploring nodes that appear more promising.
Questo's Key Terms
Sorting Algorithms: bubble sort, flag, pass, merge sort, insertion sort, quick sort, pivot
​
Seraching Algorithms: linear search, binary search, precondition
​
Pathfinding Algorithms: Dijsktra's algorithm, A* algorithm, heuristic
Did You Know?
Halo: Combat Evolved released on the Xbox in 2001 and introduced groundbreakingly convincing enemy AI for the time. Pathfinding algorithms were used more realistically than older games so that enemies wouldn't just run directly at the player but behaved in different ways depending on the situation, such as cooperating, flanking or retreating by reacting dynamically to the player.
