Searching and sorting algorithms

The specification's two searches and three sorts, each played step by step, with its code in Exam Reference Language and Python. You don't need to remember the code, but you do need to recognise it, follow it, and apply each algorithm to a list. In these examples, items.length is the number of items in the array.

Linear search

Checks each item in turn, from the start, until it finds the target or reaches the end. It works on any list, sorted or not, but may have to check every item.

linear search

Start with 7, 3, 9, 2, 6, 4.

Step 1 of 6

ERL

function linearSearch(items, target)
    for i = 0 to items.length - 1
        if items[i] == target then
            return i
        endif
    next i
    return -1
endfunction

Python

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

Binary search

The list must be sorted. It checks the middle item; if that isn't the target, it discards the half that can't contain it, and repeats on the half that's left. Halving each time makes it much faster than a linear search on a long list.

binary search

Start with 2, 4, 6, 7, 9, 12.

Step 1 of 4

ERL

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

Python

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Bubble sort

Goes through the list comparing each pair of neighbours and swapping them if they're in the wrong order. Each pass moves the largest unsorted item to the end, and the passes repeat until the list is sorted. Simple, but slow on long lists.

bubble sort

Start with 5, 1, 4, 2, 8, 3.

Step 1 of 15

ERL

procedure bubbleSort(items)
    n = items.length
    for i = 0 to n - 2
        for j = 0 to n - 2 - i
            if items[j] > items[j + 1] then
                temp = items[j]
                items[j] = items[j + 1]
                items[j + 1] = temp
            endif
        next j
    next i
endprocedure

Python

def bubble_sort(items):
    n = len(items)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if items[j] > items[j + 1]:
                temp = items[j]
                items[j] = items[j + 1]
                items[j + 1] = temp

Insertion sort

Takes each item in turn and inserts it into its place in the sorted part of the list, to its left, by moving bigger items one place right. The sorted part grows by one item each time.

insertion sort

Start with 5, 1, 4, 2, 8, 3.

Step 1 of 13

ERL

procedure insertionSort(items)
    for i = 1 to items.length - 1
        current = items[i]
        j = i - 1
        while j >= 0 AND items[j] > current
            items[j + 1] = items[j]
            j = j - 1
        endwhile
        items[j + 1] = current
    next i
endprocedure

Python

def insertion_sort(items):
    for i in range(1, len(items)):
        current = items[i]
        j = i - 1
        while j >= 0 and items[j] > current:
            items[j + 1] = items[j]
            j = j - 1
        items[j + 1] = current

Merge sort

Splits the list in half again and again until each part has one item, then merges the parts back together in order, taking the smaller front item each time, until one sorted list is left. It's usually the fastest of the three on long lists, but uses extra memory.

merge sort

Start with 5, 1, 4, 2, 8, 3.

Step 1 of 16

ERL

procedure mergeSort(items, low, high)
    if low < high then
        mid = (low + high) DIV 2
        mergeSort(items, low, mid)
        mergeSort(items, mid + 1, high)
        merge(items, low, mid, high)
    endif
endprocedure

procedure merge(items, low, mid, high)
    array temp[high - low + 1]
    i = low
    j = mid + 1
    k = 0
    while i <= mid AND j <= high
        if items[i] <= items[j] then
            temp[k] = items[i]
            i = i + 1
        else
            temp[k] = items[j]
            j = j + 1
        endif
        k = k + 1
    endwhile
    while i <= mid
        temp[k] = items[i]
        i = i + 1
        k = k + 1
    endwhile
    while j <= high
        temp[k] = items[j]
        j = j + 1
        k = k + 1
    endwhile
    for k = 0 to high - low
        items[low + k] = temp[k]
    next k
endprocedure

Python

def merge_sort(items, low, high):
    if low < high:
        mid = (low + high) // 2
        merge_sort(items, low, mid)
        merge_sort(items, mid + 1, high)
        merge(items, low, mid, high)


def merge(items, low, mid, high):
    temp = [0] * (high - low + 1)
    i = low
    j = mid + 1
    k = 0
    while i <= mid and j <= high:
        if items[i] <= items[j]:
            temp[k] = items[i]
            i = i + 1
        else:
            temp[k] = items[j]
            j = j + 1
        k = k + 1
    while i <= mid:
        temp[k] = items[i]
        i = i + 1
        k = k + 1
    while j <= high:
        temp[k] = items[j]
        j = j + 1
        k = k + 1
    for k in range(high - low + 1):
        items[low + k] = temp[k]

More in the notes: Searching algorithms and Sorting algorithms.