Standard algorithms: sorts, Dijkstra's shortest path, A*, binary search and linear search

Standard algorithms (bubble sort, insertion sort, merge sort, quick sort, Dijkstra’s shortest path algorithm, A* algorithm, binary search and linear search).

2.3.1 Algorithms

Algorithms — Note 6 of 6

Candidates need to understand the need for searching and sorting algorithms and the pre-conditions required for each. Candidates need to be able to perform, and read, trace and write code for, bubble sort, insertion sort, merge sort, quick sort, binary search and linear search. Candidates need to be able to calculate the shortest path using Dijkstra’s shortest path algorithm and the A* algorithm, and read and trace code that performs them.

What you need to know

You need to understand how each standard algorithm works, be able to carry it out by hand on a set of data, and be able to read, trace and write code for the searching and sorting algorithms. For Dijkstra's and A*, you need to read and trace code rather than write it.

What to know

Searching and sorting algorithms may have preconditions, e.g. binary search needs SORTED data.
Linear search: check each item in order until the item is found or the end is reached. Works on unsorted data. O(n).
Binary search: compare the target with the middle item; discard the half that cannot contain it; repeat until found or no items remain. Needs sorted data. O(log n).
Bubble sort: repeatedly pass through the list, swapping adjacent items that are in the wrong order, until a pass makes no swaps. O(n²).
Insertion sort: take each item in turn and insert it into the correct position within the sorted part of the list. O(n²), but fast for nearly sorted data.
Merge sort: split the list in half repeatedly until each part has one item, then merge pairs of sorted lists back together in order. O(n log n), needs extra memory.
Quick sort: choose a pivot; partition the list into items smaller than and larger than the pivot; recursively sort each part. Average O(n log n), worst O(n²).
Dijkstra's algorithm: finds the shortest path from a start node to every other node in a weighted graph. Repeatedly visit the unvisited node with the smallest known distance, and update the distances to its neighbours if a shorter route is found.
A* algorithm: finds the shortest path between two nodes, using f = g + h, where g is the actual cost from the start and h is a heuristic estimate of the remaining cost (e.g. straight-line distance). The node with the lowest f is explored next, so A* usually explores fewer nodes than Dijkstra's.

Exam technique

Tip:For Dijkstra's and A*, show the table of distances (and heuristics) at each step, and the order in which nodes are visited.
Mistake:Using binary search on unsorted data.

Code examples

Binary search (iterative) in OCR pseudocode

text

function binarySearch(list, target)
    low = 0
    high = list.length - 1
    while low <= high
        mid = (low + high) DIV 2
        if list[mid] == target then
            return mid
        elseif list[mid] < target then
            low = mid + 1
        else
            high = mid - 1
        endif
    endwhile
    return -1
endfunction

Bubble sort with a swapped flag

python

def bubble_sort(data):
    swapped = True
    passes = 0
    while swapped:
        swapped = False
        for i in range(len(data) - 1 - passes):
            if data[i] > data[i + 1]:
                data[i], data[i + 1] = data[i + 1], data[i]
                swapped = True
        passes += 1
    return data

Insertion sort

python

def insertion_sort(data):
    for i in range(1, len(data)):
        current = data[i]
        pos = i
        while pos > 0 and data[pos - 1] > current:
            data[pos] = data[pos - 1]   # shift larger items right
            pos -= 1
        data[pos] = current
    return data

Merge sort

python

def merge_sort(data):
    if len(data) <= 1:
        return data
    mid = len(data) // 2
    left = merge_sort(data[:mid])
    right = merge_sort(data[mid:])
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    return result + left[i:] + right[j:]

Quick sort

python

def quick_sort(data):
    if len(data) <= 1:
        return data
    pivot = data[0]
    smaller = [x for x in data[1:] if x < pivot]
    larger = [x for x in data[1:] if x >= pivot]
    return quick_sort(smaller) + [pivot] + quick_sort(larger)

Dijkstra's shortest path algorithm

python

def dijkstra(graph, start):
    # graph: {node: {neighbour: weight}}
    distances = {node: float("inf") for node in graph}
    distances[start] = 0
    unvisited = list(graph)
    while unvisited:
        current = min(unvisited, key=lambda n: distances[n])
        unvisited.remove(current)
        for neighbour, weight in graph[current].items():
            new_distance = distances[current] + weight
            if new_distance < distances[neighbour]:
                distances[neighbour] = new_distance
    return distances

graph = {"A": {"B": 4, "C": 1}, "B": {"D": 1},
         "C": {"B": 2, "D": 5}, "D": {}}
print(dijkstra(graph, "A"))   # {'A': 0, 'B': 3, 'C': 1, 'D': 4}