CS · Chapter 23

Cambridge AS & A Level · Part 4 · Chapter 23

Algorithms

The standard ways to search, sort and store data: two searches, two sorts, six abstract data types, and Big O notation for comparing them. Every pseudocode listing, task and exam question from the chapter is here, with a simulator for each structure.

Guru Jazzy

🎯 Learning objectives

By the end of this chapter you should be able to:

explain linear and binary searching, and write an algorithm for each
state the condition a binary search needs (the list must be ordered)
explain how a binary search's performance changes with the number of items
Explain insertion sort and bubble sort
explain why a sort's performance depends on the initial order and the number of items
explain and use abstract data types (ADTs), and show how one ADT can be built from another
describe stacks, queues, linked lists, dictionaries and binary trees, and implement them from built-in types or other ADTs

write algorithms to:
- implement an insertion sort and a bubble sort
- find an item in a linked list and a binary tree
- insert an item into a stack, queue, linked list and binary tree
- delete an item from a stack, queue and linked list
explain that a graph is an ADT, describe its key features and justify using one
compare algorithms that do the same job by the time they take and the memory they use
use Big O notation for time and space complexity

🔦 23.01 Linear search

You met the linear search algorithm in Chapter 13 (Worked Example 13.02): start at the first element and check each one in turn until you find the item or run out of list.

Discussion point: What were the essential features of a linear search?

It checks the elements one at a time, in order, from the start.
It stops as soon as the item is found, or when the end of the list is reached.
It works on an unordered list. It is the only systematic way to search one.
In the worst case it makes n comparisons for n items.

Task 23.01 Write program code for the linear search algorithm. Assume that the items to be searched are stored in a 1D array with n elements.

def linear_search(my_list, search_item):
    index = 0
    found = False
    while index < len(my_list) and not found:
        if my_list[index] == search_item:
            found = True
        else:
            index = index + 1
    if found:
        return index        # position where the item was found
    return -1               # not in the list

print(linear_search([12, 5, 31, 8, 22], 8))   # 3

🫧 23.02 Bubble sort

You met the bubble sort in Chapter 13 (Worked Example 13.03). Each pass compares neighbouring pairs and swaps any that are in the wrong order, so the largest unsorted value "bubbles" to the end.

Discussion point: What were the essential features of a bubble sort?

It compares each pair of adjacent items and swaps them if they are out of order.
After each pass, the largest remaining item is in its final place, so the next pass can stop one place earlier.
The efficient version keeps a flag: if a whole pass makes no swaps, the list is sorted and it stops early.
It sorts in place, using only one temporary variable for the swap.

Task 23.02 Write program code for the most efficient bubble sort algorithm. Assume that the items to be sorted are stored in a 1D array with n elements.

def bubble_sort(my_list):
    unsorted = len(my_list) - 1      # last index still to sort
    swapped = True
    while swapped and unsorted > 0:
        swapped = False
        for j in range(unsorted):    # j = 0 .. unsorted - 1
            if my_list[j] > my_list[j + 1]:
                my_list[j], my_list[j + 1] = my_list[j + 1], my_list[j]
                swapped = True
        unsorted = unsorted - 1      # one more item is now in place

data = [47, 6, 54, 17, 93, 28]
bubble_sort(data)
print(data)   # [6, 17, 28, 47, 54, 93]

Two things make it "most efficient": each pass is one comparison shorter than the last, and the swapped flag stops the sort as soon as a pass makes no swaps.

🃏 23.03 Insertion sort Figure 23.01

Imagine a set of cards, each with a different value. How would you sort them into increasing order?

Think of the pile as two parts: a sorted part in your hand and an unsorted pile on the table. At first only the top card is "sorted". The card on top of the table pile is the next one to insert. The last (bottom) card in your hand is your current card.

**Figure 23.01**Sorting cards: the sorted cards in your hand (blue), the next card to insert (red) and the unsorted pile (white)

Repeat until every card from the unsorted pile has been inserted in its correct position:

Repeat until the card to be inserted is in its correct position:
1. Compare the current card with the card to be inserted.
2. If the card to be inserted is greater than the current card, insert it below the current card.
3. Otherwise, if there is a card above the current card in your hand, make that your new current card.
4. If there is no new current card, put the card to be inserted at the top of the sorted pile.

In effect, every card you look at that is bigger than the new card moves down one place. If the new card is smaller than every card you check, it ends up at the top (position 0). This is the insertion sort, a standard method. In pseudocode, with the values in a 1D array List:

FOR Pointer ← 1 TO NumberOfitems - 1
    ItemToBeInserted ← List[Pointer]
    CurrentItem ← Pointer - 1  // pointer to last item in sorted part of list
    WHILE (List[CurrentItem] > ItemToBeInserted) AND (CurrentItem > -1) DO
        List[CurrentItem + 1] ← List[CurrentItem]  // move current item down
        CurrentItem ← CurrentItem - 1  // look at the item above
    ENDWHILE
    List[CurrentItem + 1] ← ItemToBeInserted  // insert item
NEXT Pointer

Watch the WHILE condition. When CurrentItem reaches −1, the book's order evaluates List[-1] before checking CurrentItem > -1. Pseudocode does not say whether AND short-circuits, so in real code put the bounds check first: WHILE CurrentItem > -1 AND List[CurrentItem] > ItemToBeInserted. In Python, my_list[-1] silently reads the last element instead of failing.

🔬 Lab: watch bubble sort and insertion sort

Pick a sort and a starting order, then step through or run it. Amber bars are being compared; red bars are moving.

Sort Start Items 12

Comparisons: 0Moves: 0

Press Step to begin.

Task 23.03

Dry-run the insertion sort algorithm using a trace table. Assume the list holds these six items in this order: 53, 21, 60, 18, 42, 19.
Write program code for the insertion sort algorithm. Assume that the items to be sorted are stored in a 1D array with n elements.

🧾 Trace-table maker

Do the dry run on paper first, then compare. The table adds a row every time a variable or array element changes.

def insertion_sort(my_list):
    for pointer in range(1, len(my_list)):
        item_to_be_inserted = my_list[pointer]
        current_item = pointer - 1
        # bounds check first, so my_list[-1] is never read
        while current_item > -1 and my_list[current_item] > item_to_be_inserted:
            my_list[current_item + 1] = my_list[current_item]
            current_item = current_item - 1
        my_list[current_item + 1] = item_to_be_inserted

data = [53, 21, 60, 18, 42, 19]
insertion_sort(data)
print(data)   # [18, 19, 21, 42, 53, 60]

Extension question 23.01: Investigate the performances of the insertion sort and the bubble sort by (a) varying the initial order of the items and (b) increasing the number of items to be sorted.

🏁 Race the two sorts

Counts of comparisons for each sort, run on the same lists. Press the button for fresh random lists.

What to notice: on a sorted list both sorts make only n − 1 comparisons (the flag stops bubble sort after one pass). On a reversed list both make n(n − 1)/2. On random lists insertion sort usually needs about half the comparisons of bubble sort, and doubling n roughly quadruples the count for both.

🔎 23.04 Binary search

Section 23.01 used a linear search. It is the only systematic way to search an unordered list. If the list is ordered, there is a faster technique.

Think about looking up "quicksort" in a paper dictionary. You would not start at page 1. You open it near the middle and find "magnetic". "Quicksort" comes after "magnetic", so it must be in the second half. In the middle of that half you find "report". "Quicksort" comes before "report", so it is in the third quarter. You keep checking the middle of the part that must contain your word until you find it. If the word is not in the dictionary, you eventually run out of entries to check.

Binary search: repeatedly checking the middle item in an ordered search list and discarding the half of the list that does not contain the search item.

In pseudocode, with the values sorted into ascending order in a 1D array List of size MaxItems:

Found ← FALSE
SearchFailed ← FALSE
First ← 0
Last ← MaxItems - 1 // set boundaries of search area
WHILE NOT Found AND NOT SearchFailed DO
    Middle ← (First + Last) DIV 2 // find middle of current search area
    IF List[Middle] = SearchItem
      THEN
        Found ← TRUE
      ELSE
        IF First >= Last // no search area left
          THEN
            SearchFailed ← TRUE
          ELSE
            IF List[Middle] > SearchItem
              THEN // must be in first half
                Last ← Middle - 1  // move upper boundary
              ELSE // must be in second half
                First ← Middle + 1  // move lower boundary
            ENDIF
        ENDIF
    ENDIF
ENDWHILE
IF Found = TRUE
  THEN
    OUTPUT Middle // output position where item was found
  ELSE
    OUTPUT "Item not present in array"
ENDIF

Edge case in the book's version. The test First >= Last happens before the boundary moves, so First can end up one past Last. Searching a two-item list for a value smaller than both gives Last ← -1, and the next pass reads List[(0 + -1) DIV 2], which is outside the array. The safe version tests the boundaries in the loop condition: WHILE NOT Found AND First <= Last DO. The lab below uses the safe version. For the book's 20-item list both versions give the same answers.

Task 23.04

Dry-run the binary search algorithm using a trace table. Assume the list holds these 20 items in this order: 7, 12, 19, 23, 27, 33, 37, 41, 45, 56, 59, 60, 62, 71, 75, 80, 84, 88, 92, 99.
Search for the value 60. How many times did you have to execute the WHILE loop?
Dry-run the algorithm again, this time searching for the value 34. How many times did you have to execute the WHILE loop?

🔬 Lab: binary search stepper

The book's 20 items are loaded. Type a value and step through. Grey cells have been discarded; amber is Middle.

Search for

Loop pass	First	Last	Middle	List[Middle]	Decision

Index the list from 0: List[9] = 56, List[11] = 60, List[14] = 75.

Search for 60
Pass	First	Last	Middle	List[Middle]
1	0	19	9	56 < 60 → First ← 10
2	10	19	14	75 > 60 → Last ← 13
3	10	13	11	60 = 60 → Found

2: the WHILE loop runs 3 times.

Search for 34
Pass	First	Last	Middle	List[Middle]
1	0	19	9	56 > 34 → Last ← 8
2	0	8	4	27 < 34 → First ← 5
3	5	8	6	37 > 34 → Last ← 5
4	5	5	5	33 ≠ 34 and First >= Last → SearchFailed

3: the WHILE loop runs 4 times, then outputs "Item not present in array".

Discussion point: Compare the binary search with the linear search. If the array holds n items, how many times on average do you need to test a value with each search? How does the search time change as n grows?

📏 Linear vs binary: how many checks?

n =

Linear search: about n/2 tests on average when the item is present, and n when it is not. The time grows in proportion to n, so doubling the list doubles the time.
Binary search: at most about log₂ n + 1 tests, because each test halves what is left. Doubling the list adds only one more test. A million items need about 20 tests.
The price is that binary search needs the list to be sorted first, and sorting takes time.

🧩 23.05 Abstract Data Types (ADTs)

Chapter 13 (Sections 13.07–13.10) introduced ADTs with conceptual diagrams and showed how to implement them with arrays. This chapter writes the code for their basic operations.

Abstract data type (ADT): a collection of data together with a set of operations on that data. You care about what the operations do (insert, find, delete), not how they are stored. That is why one ADT can be built from another: a stack or a queue can be built from an array or from a linked list.

🎮 Which ADT fits?

🔗 23.06 Linked lists

Look back at Chapter 13, Section 13.10. An empty linked list has its StartPointer set to the null pointer, and a free list links all the empty nodes. Here is the code for the basic operations drawn in the conceptual diagrams (Figures 13.11 to 13.16).

Create a new linked list

// NullPointer should be set to -1 if using array element with index 0
CONSTANT NullPointer = -1
// Declare record type to store data and pointer
TYPE ListNode
    DECLARE Data    : STRING
    DECLARE Pointer : INTEGER
ENDTYPE
DECLARE StartPointer : INTEGER
DECLARE FreeListPtr  : INTEGER
DECLARE List : ARRAY[0 : 6] OF ListNode

PROCEDURE InitialiseList
    StartPointer ← NullPointer      // set start pointer
    FreeListPtr ← 0                 // set starting position of free list
    FOR Index ← 0 TO 5              // link all nodes to make free list
        List[Index].Pointer ← Index + 1
    NEXT Index
    List[6].Pointer ← NullPointer   // last node of free list
ENDPROCEDURE

Insert a new node into an ordered linked list

PROCEDURE InsertNode(NewItem)
    IF FreeListPtr <> NullPointer
      THEN  // there is space in the array
        // take node from free list and store data item
        NewNodePtr ← FreeListPtr
        List[NewNodePtr].Data ← NewItem
        FreeListPtr ← List[FreeListPtr].Pointer
        // find insertion point
        ThisNodePtr ← StartPointer  // start at beginning of list
        PreviousNodePtr ← NullPointer
        WHILE ThisNodePtr <> NullPointer  // while not end of list
          AND List[ThisNodePtr].Data < NewItem DO
            PreviousNodePtr ← ThisNodePtr  // remember this node
            // follow the pointer to the next node
            ThisNodePtr ← List[ThisNodePtr].Pointer
        ENDWHILE
        IF PreviousNodePtr = NullPointer
          THEN  // insert new node at start of list
            List[NewNodePtr].Pointer ← StartPointer
            StartPointer ← NewNodePtr
          ELSE  // insert new node between previous node and this node
            List[NewNodePtr].Pointer ← List[PreviousNodePtr].Pointer
            List[PreviousNodePtr].Pointer ← NewNodePtr
        ENDIF
    ENDIF
ENDPROCEDURE

Book error fixed. The book prints IF PreviousNodePtr = StartPointer. It should be IF PreviousNodePtr = NullPointer: the new node goes at the start only when the loop never moved past a node. With the printed line, inserting D after B makes D point back to B and become the start, so the list reads D → B. You can try the printed version in the lab below.

After three data items have been added, the array looks like Figure 23.02.

**Figure 23.02**Linked list of three nodes and a free list of four nodes

Find an element in an ordered linked list

FUNCTION FindNode(DataItem) RETURNS INTEGER  // returns pointer to node
    CurrentNodePtr ← StartPointer  // start at beginning of list
    WHILE CurrentNodePtr <> NullPointer  // not end of list
      AND List[CurrentNodePtr].Data <> DataItem DO  // item not found
        // follow the pointer to the next node
        CurrentNodePtr ← List[CurrentNodePtr].Pointer
    ENDWHILE
    RETURN CurrentNodePtr  // returns NullPointer if item not found
ENDFUNCTION

Delete a node from an ordered linked list

PROCEDURE DeleteNode(DataItem)
    ThisNodePtr ← StartPointer               // start at beginning of list
    WHILE ThisNodePtr <> NullPointer         // while not end of list
      AND List[ThisNodePtr].Data <> DataItem DO // and item not found
        PreviousNodePtr ← ThisNodePtr   // remember this node
        // follow the pointer to the next node
        ThisNodePtr ← List[ThisNodePtr].Pointer
    ENDWHILE
    IF ThisNodePtr <> NullPointer  // node exists in list
      THEN
        IF ThisNodePtr = StartPointer // first node to be deleted
          THEN
            // move start pointer to the next node in list
            StartPointer ← List[StartPointer].Pointer
          ELSE
            // it is not the start node;
            // so make the previous node's pointer point to
            // the current node's 'next' pointer; thereby removing all
            // references to the current pointer from the list
            List[PreviousNodePtr].Pointer ← List[ThisNodePtr].Pointer
        ENDIF
        List[ThisNodePtr].Pointer ← FreeListPtr
        FreeListPtr ← ThisNodePtr
    ENDIF
ENDPROCEDURE

Access all nodes stored in the linked list

PROCEDURE OutputAllNodes
    CurrentNodePtr ← StartPointer // start at beginning of list
    WHILE CurrentNodePtr <> NullPointer DO // while not end of list
        OUTPUT List[CurrentNodePtr].Data
        // follow the pointer to the next node
        CurrentNodePtr ← List[CurrentNodePtr].Pointer
    ENDWHILE
ENDPROCEDURE

🔬 Lab: linked list in an array

This runs the procedures above on a 7-node array. Load the book's example to get Figure 23.02, then insert, find and delete. Watch how only pointers change; data never moves.

Use the book's printed line (= StartPointer)

Index	Data	Pointer	On…

Task 23.05 Convert the pseudocode for the linked-list handling subroutines to program code. Incorporate the subroutines into a program and test them.

NULL_POINTER = -1

class ListNode:
    def __init__(self):
        self.data = ""
        self.pointer = NULL_POINTER

my_list = [ListNode() for _ in range(7)]
start_pointer = NULL_POINTER
free_list_ptr = 0

def initialise_list():
    global start_pointer, free_list_ptr
    start_pointer = NULL_POINTER
    free_list_ptr = 0
    for index in range(6):
        my_list[index].pointer = index + 1
    my_list[6].pointer = NULL_POINTER

def insert_node(new_item):
    global start_pointer, free_list_ptr
    if free_list_ptr == NULL_POINTER:
        print("List full")
        return
    new_node_ptr = free_list_ptr
    my_list[new_node_ptr].data = new_item
    free_list_ptr = my_list[free_list_ptr].pointer
    this_node_ptr = start_pointer
    previous_node_ptr = NULL_POINTER
    while this_node_ptr != NULL_POINTER and my_list[this_node_ptr].data < new_item:
        previous_node_ptr = this_node_ptr
        this_node_ptr = my_list[this_node_ptr].pointer
    if previous_node_ptr == NULL_POINTER:      # insert at start
        my_list[new_node_ptr].pointer = start_pointer
        start_pointer = new_node_ptr
    else:                                      # insert in the middle or at the end
        my_list[new_node_ptr].pointer = my_list[previous_node_ptr].pointer
        my_list[previous_node_ptr].pointer = new_node_ptr

def find_node(data_item):
    current = start_pointer
    while current != NULL_POINTER and my_list[current].data != data_item:
        current = my_list[current].pointer
    return current

def delete_node(data_item):
    global start_pointer, free_list_ptr
    this_node_ptr = start_pointer
    previous_node_ptr = NULL_POINTER
    while this_node_ptr != NULL_POINTER and my_list[this_node_ptr].data != data_item:
        previous_node_ptr = this_node_ptr
        this_node_ptr = my_list[this_node_ptr].pointer
    if this_node_ptr != NULL_POINTER:
        if this_node_ptr == start_pointer:
            start_pointer = my_list[start_pointer].pointer
        else:
            my_list[previous_node_ptr].pointer = my_list[this_node_ptr].pointer
        my_list[this_node_ptr].pointer = free_list_ptr
        free_list_ptr = this_node_ptr

def output_all_nodes():
    current = start_pointer
    while current != NULL_POINTER:
        print(my_list[current].data)
        current = my_list[current].pointer

# test
initialise_list()
for item in ["D", "B", "L"]:
    insert_node(item)
output_all_nodes()            # B D L
print(find_node("D"))         # 0 (D was stored first, in node 0)
delete_node("B")
output_all_nodes()            # D L

Test plan ideas: insert into an empty list, at the start, in the middle and at the end; insert when full; find a present and an absent item; delete the first, a middle and the last node, and an item that is not there.

A stack and a queue can be treated as special cases of a linked list. A linked-list stack only adds and removes nodes at the front (Section 23.08). A linked-list queue adds nodes at the end and removes them from the front (Section 23.09).

🌳 23.07 Binary trees Figures 23.03–23.05

In real life we draw trees to show hierarchies, such as a family tree of ancestors and children. A binary tree is different because each node can have at most two children.

Binary trees have several uses in computer science. Chapter 20 (Section 20.06) used one as a syntax tree. This chapter uses an ordered binary tree ADT, like Figure 23.03, as a binary search tree.

**Figure 23.03**Conceptual diagram of an ordered binary tree: root node, parent/child node, leaf node, left and right subtrees

Nodes are added to an ordered binary tree in a fixed way:

Start at the root node as the current node.
Repeat
    If the data value is greater than the current node's data value, follow the right branch.
    If the data value is smaller than the current node's data value, follow the left branch.
Until the current node has no branch to follow.
Add the new node in this position.

For example, to add D to the tree in Figure 23.03:

Start at the root node.
D is smaller than F, so turn left.
D is greater than C, so turn right.
D is smaller than E, so turn left.
There is no branch going left from E, so add D as the left child of E (Figure 23.04).

**Figure 23.04**Adding D to the ordered binary tree: it becomes the left child of E

This kind of tree is useful as a search tree. Like a binary search on an ordered list, it is faster to search than a linear list or a linked list. It also makes adding a node easy: no other nodes move. Only one left or right pointer changes to link the new node in.

The tree can be stored in an array of records (Figure 23.05). Each record is a node holding the data, a left pointer and a right pointer. Unused nodes are linked together into a free list.

**Figure 23.05**Binary tree stored in an array before any nodes are inserted: every node is on the free list

Create a new binary tree

// NullPointer should be set to -1 if using array element with index 0
CONSTANT NullPointer = -1
// Declare record type to store data and pointers
TYPE TreeNode
    DECLARE Data : STRING
    DECLARE LeftPointer : INTEGER
    DECLARE RightPointer : INTEGER
ENDTYPE
DECLARE RootPointer : INTEGER
DECLARE FreePtr : INTEGER
DECLARE Tree : ARRAY[0 : 6] OF TreeNode
PROCEDURE InitialiseTree
    RootPointer ← NullPointer  // set start pointer
    FreePtr ← 0                // set starting position of free list
    FOR Index ← 0 TO 5         // link all nodes to make free list
        Tree[Index].LeftPointer ← Index + 1
    NEXT Index
    Tree[6].LeftPointer ← NullPointer // last node of free list
ENDPROCEDURE

Insert a new node into a binary tree

PROCEDURE InsertNode(NewItem)
    IF FreePtr <> NullPointer
      THEN  // there is space in the array
        // take node from free list, store data item, set null pointers
        NewNodePtr ← FreePtr
        FreePtr ← Tree[FreePtr].LeftPointer
        Tree[NewNodePtr].Data ← NewItem
        Tree[NewNodePtr].LeftPointer ← NullPointer
        Tree[NewNodePtr].RightPointer ← NullPointer
        // check if empty tree
        IF RootPointer = NullPointer
          THEN  // insert new node at root
            RootPointer ← NewNodePtr
          ELSE  // find insertion point
            ThisNodePtr ← RootPointer   // start at the root of the tree
            WHILE ThisNodePtr <> NullPointer DO  // while not a leaf node
                PreviousNodePtr ← ThisNodePtr  // remember this node
                IF Tree[ThisNodePtr].Data > NewItem
                  THEN  // follow left pointer
                    TurnedLeft ← TRUE
                    ThisNodePtr ← Tree[ThisNodePtr].LeftPointer
                  ELSE // follow right pointer
                    TurnedLeft ← FALSE
                    ThisNodePtr ← Tree[ThisNodePtr].RightPointer
                ENDIF
            ENDWHILE
            IF TurnedLeft = TRUE
              THEN
                Tree[PreviousNodePtr].LeftPointer ← NewNodePtr
              ELSE
                Tree[PreviousNodePtr].RightPointer ← NewNodePtr
            ENDIF
        ENDIF
    ENDIF
ENDPROCEDURE

Find a node in a binary tree

FUNCTION FindNode(SearchItem) RETURNS INTEGER  // returns pointer to node
    ThisNodePtr ← RootPointer       // start at the root of the tree
    WHILE ThisNodePtr <> NullPointer   // while a pointer to follow
      AND Tree[ThisNodePtr].Data <> SearchItem DO // and search item not found
        IF Tree[ThisNodePtr].Data > SearchItem
          THEN  // follow left pointer
            ThisNodePtr ← Tree[ThisNodePtr].LeftPointer
          ELSE // follow right pointer
            ThisNodePtr ← Tree[ThisNodePtr].RightPointer
        ENDIF
    ENDWHILE
    RETURN ThisNodePtr // will return null pointer if search item not found
ENDFUNCTION

🔬 Lab: binary search tree in an array

Insert letters (or numbers) and watch the tree and the array grow. The array has 7 nodes, like the book's. Load F C S B E R D to rebuild Figure 23.04.

Index	LeftPointer	Data	RightPointer

Task 23.06 Write program code to implement a binary search tree.

NULL_POINTER = -1

class TreeNode:
    def __init__(self):
        self.data = ""
        self.left_pointer = NULL_POINTER
        self.right_pointer = NULL_POINTER

tree = [TreeNode() for _ in range(7)]
root_pointer = NULL_POINTER
free_ptr = 0

def initialise_tree():
    global root_pointer, free_ptr
    root_pointer = NULL_POINTER
    free_ptr = 0
    for index in range(6):
        tree[index].left_pointer = index + 1
    tree[6].left_pointer = NULL_POINTER

def insert_node(new_item):
    global root_pointer, free_ptr
    if free_ptr == NULL_POINTER:
        print("Tree full")
        return
    new_node_ptr = free_ptr
    free_ptr = tree[free_ptr].left_pointer
    tree[new_node_ptr].data = new_item
    tree[new_node_ptr].left_pointer = NULL_POINTER
    tree[new_node_ptr].right_pointer = NULL_POINTER
    if root_pointer == NULL_POINTER:
        root_pointer = new_node_ptr
        return
    this_node_ptr = root_pointer
    while this_node_ptr != NULL_POINTER:
        previous_node_ptr = this_node_ptr
        if tree[this_node_ptr].data > new_item:
            turned_left = True
            this_node_ptr = tree[this_node_ptr].left_pointer
        else:
            turned_left = False
            this_node_ptr = tree[this_node_ptr].right_pointer
    if turned_left:
        tree[previous_node_ptr].left_pointer = new_node_ptr
    else:
        tree[previous_node_ptr].right_pointer = new_node_ptr

def find_node(search_item):
    this_node_ptr = root_pointer
    while this_node_ptr != NULL_POINTER and tree[this_node_ptr].data != search_item:
        if tree[this_node_ptr].data > search_item:
            this_node_ptr = tree[this_node_ptr].left_pointer
        else:
            this_node_ptr = tree[this_node_ptr].right_pointer
    return this_node_ptr

def in_order(ptr):              # bonus: prints the items in order
    if ptr != NULL_POINTER:
        in_order(tree[ptr].left_pointer)
        print(tree[ptr].data)
        in_order(tree[ptr].right_pointer)

initialise_tree()
for letter in "FCSBERD":
    insert_node(letter)
print(find_node("E"))   # 4
in_order(root_pointer)  # B C D E F R S

📚 23.08 Stacks Figure 23.06

Chapter 13 (Section 13.08) showed the conceptual structure of a stack. A stack can be implemented with a 1D array. Figure 23.06 shows a stack holding four items. For conceptual reasons the elements are numbered from the bottom up.

**Figure 23.06**A stack holding A–D, numbered from the bottom up, with BaseOfStackPointer and TopOfStackPointer

BaseOfStackPointer always points to element 0. TopOfStackPointer changes: it goes up when an item is pushed and down when one is popped. When the stack is empty, TopOfStackPointer is −1. A stack is last in, first out (LIFO).

Create a new stack

// NullPointer should be set to -1 if using array element with index 0
CONSTANT EMPTYSTRING = ""
CONSTANT NullPointer = -1
CONSTANT MaxStackSize = 8
DECLARE BaseOfStackPointer : INTEGER
DECLARE TopOfStackPointer : INTEGER
DECLARE Stack : ARRAY[0 : MaxStackSize - 1] OF STRING

PROCEDURE InitialiseStack
    BaseOfStackPointer ← 0           // set base of stack pointer
    TopOfStackPointer ← NullPointer  // set top of stack pointer
ENDPROCEDURE

Book error fixed. The book declares Stack : ARRAY[1 : MaxStackSize - 1]. That has only 7 elements and no element 0, yet the base pointer is 0 and the first push writes to Stack[0]. The lower bound must be 0.

Push an item onto the stack

PROCEDURE Push(NewItem)
    IF TopOfStackPointer < MaxStackSize - 1
      THEN  // there is space on the stack
            // increment top of stack pointer
        TopOfStackPointer ← TopOfStackPointer + 1
            // add item to top of stack
        Stack[TopOfStackPointer] ← NewItem
    ENDIF
ENDPROCEDURE

Pop an item off the stack

FUNCTION Pop()
    DECLARE Item : STRING
    Item ← EMPTYSTRING
    IF TopOfStackPointer > NullPointer
      THEN  // there is at least one item on the stack
            // pop item off the top of the stack
        Item ← Stack[TopOfStackPointer]
            // decrement top of stack pointer
        TopOfStackPointer ← TopOfStackPointer - 1
    ENDIF
    RETURN Item
ENDFUNCTION

🔬 Lab: stack in an array

Task 23.07

Write a program to implement the pseudocode subroutines above. Add a menu to test them.
Write a program to implement a stack as a linked list. Note that adding and removing nodes is much simpler than for an ordered linked list.

1. Array stack with a menu

MAX_STACK_SIZE = 8
NULL_POINTER = -1
stack = [""] * MAX_STACK_SIZE
base_of_stack_pointer = 0
top_of_stack_pointer = NULL_POINTER

def push(new_item):
    global top_of_stack_pointer
    if top_of_stack_pointer < MAX_STACK_SIZE - 1:
        top_of_stack_pointer += 1
        stack[top_of_stack_pointer] = new_item
    else:
        print("Stack full")

def pop():
    global top_of_stack_pointer
    item = ""
    if top_of_stack_pointer > NULL_POINTER:
        item = stack[top_of_stack_pointer]
        top_of_stack_pointer -= 1
    else:
        print("Stack empty")
    return item

while True:
    choice = input("1 Push  2 Pop  3 Show  4 Quit: ")
    if choice == "1":
        push(input("Item: "))
    elif choice == "2":
        print("Popped:", pop())
    elif choice == "3":
        print(stack[:top_of_stack_pointer + 1])
    elif choice == "4":
        break

2. Linked-list stack: push and pop only ever touch the front node, so there is no searching.

NULL_POINTER = -1
data = [""] * 8
pointer = [i + 1 for i in range(8)]
pointer[7] = NULL_POINTER
top_ptr = NULL_POINTER          # front of the linked list
free_ptr = 0

def push(new_item):
    global top_ptr, free_ptr
    if free_ptr == NULL_POINTER:
        print("Stack full")
        return
    new_node = free_ptr
    free_ptr = pointer[free_ptr]
    data[new_node] = new_item
    pointer[new_node] = top_ptr     # new node points at the old top
    top_ptr = new_node

def pop():
    global top_ptr, free_ptr
    if top_ptr == NULL_POINTER:
        return ""                   # empty
    node = top_ptr
    top_ptr = pointer[node]         # next node becomes the top
    pointer[node] = free_ptr        # return node to the free list
    free_ptr = node
    return data[node]

🚶 23.09 Queues Figures 23.07–23.08

Chapter 13 (Section 13.09) showed the conceptual structure of a queue. A queue can be implemented with a 1D array. Figure 23.07 shows a queue holding five items.

FrontOfQueuePointer always points to the first element in the queue: the next one to be taken off. EndOfQueuePointer always points to the last element. Before a new element joins, EndOfQueuePointer is incremented. Whenever either pointer moves, you have to check for wrap-round: going past the last element back to element 0. A queue is first in, first out (FIFO).

A counter variable makes it easy to test whether the queue is empty or full.

**Figures 23.07 and 23.08**A queue before wrap-round (left) and with wrap-round (right)

Create a new queue

// NullPointer should be set to -1 if using array element with index 0
CONSTANT EMPTYSTRING = ""
CONSTANT NullPointer = -1
CONSTANT MaxQueueSize = 8
DECLARE FrontOfQueuePointer : INTEGER
DECLARE EndOfQueuePointer : INTEGER
DECLARE NumberInQueue : INTEGER
DECLARE Queue : ARRAY[0 : MaxQueueSize - 1] OF STRING
PROCEDURE InitialiseQueue
    FrontOfQueuePointer ← NullPointer   // set front of queue pointer
    EndOfQueuePointer ← NullPointer     // set end of queue pointer
    NumberInQueue ← 0                   // no elements in queue
ENDPROCEDURE

Add an item to the queue

PROCEDURE AddToQueue(NewItem)
    IF NumberInQueue < MaxQueueSize
      THEN    // there is space in the queue
              // increment end of queue pointer
        EndOfQueuePointer ← EndOfQueuePointer + 1
              // check for wrap-round
        IF EndOfQueuePointer > MaxQueueSize - 1
          THEN   // wrap to beginning of array
            EndOfQueuePointer ← 0
                 // add item to end of queue
        ENDIF
        Queue[EndOfQueuePointer] ← NewItem
         // increment counter
        NumberInQueue ← NumberInQueue + 1
    ENDIF
ENDPROCEDURE

Remove an item from the queue

FUNCTION RemoveFromQueue()
    DECLARE Item : STRING
    Item ← EMPTYSTRING
    IF NumberInQueue > 0
      THEN // there is at least one item in the queue
           // remove item from the front of the queue
        Item ← Queue[FrontOfQueuePointer]
        NumberInQueue ← NumberInQueue - 1
        IF NumberInQueue = 0
          THEN // if queue empty, reset pointers
            CALL InitialiseQueue
          ELSE
            // increment front of queue pointer
            FrontOfQueuePointer ← FrontOfQueuePointer + 1
            // check for wrap-round
            IF FrontOfQueuePointer > MaxQueueSize - 1
              THEN // wrap to beginning of array
                FrontOfQueuePointer ← 0
            ENDIF
        ENDIF
    ENDIF
    RETURN Item
ENDFUNCTION

Missing step in the book's code. InitialiseQueue sets FrontOfQueuePointer to −1, and AddToQueue never changes it. So after the first item joins an empty queue, RemoveFromQueue would read Queue[-1]. Add this inside AddToQueue, after the item is stored: IF NumberInQueue = 1 THEN FrontOfQueuePointer ← EndOfQueuePointer ENDIF (or initialise the front pointer to 0 instead of −1). The lab below includes the fix.

🔬 Lab: circular queue

Add and remove items until the end pointer wraps round to element 0, as in Figure 23.08.

Task 23.08

Write a program to implement the pseudocode subroutines above. Add a menu to test them.
Write program code to implement a queue as a linked list. You may find it helpful to add another pointer that always points to the end of the queue. You will need to update it when you add a new node.

1. Circular array queue (a menu loop like Task 23.07's calls these):

MAX_QUEUE_SIZE = 8
NULL_POINTER = -1
queue = [""] * MAX_QUEUE_SIZE

def initialise_queue():
    global front, end, number_in_queue
    front = NULL_POINTER
    end = NULL_POINTER
    number_in_queue = 0

def add_to_queue(new_item):
    global front, end, number_in_queue
    if number_in_queue < MAX_QUEUE_SIZE:
        end = end + 1
        if end > MAX_QUEUE_SIZE - 1:
            end = 0                         # wrap round
        queue[end] = new_item
        number_in_queue += 1
        if number_in_queue == 1:
            front = end                     # first item is also the front
    else:
        print("Queue full")

def remove_from_queue():
    global front, number_in_queue
    item = ""
    if number_in_queue > 0:
        item = queue[front]
        number_in_queue -= 1
        if number_in_queue == 0:
            initialise_queue()
        else:
            front = front + 1
            if front > MAX_QUEUE_SIZE - 1:
                front = 0                   # wrap round
    return item

initialise_queue()

2. Linked-list queue: join at the end node, leave from the front node.

NULL_POINTER = -1
data = [""] * 8
pointer = [i + 1 for i in range(8)]
pointer[7] = NULL_POINTER
front_ptr = NULL_POINTER
end_ptr = NULL_POINTER
free_ptr = 0

def join_queue(new_item):
    global front_ptr, end_ptr, free_ptr
    if free_ptr == NULL_POINTER:
        print("Queue full")
        return
    new_node = free_ptr
    free_ptr = pointer[free_ptr]
    data[new_node] = new_item
    pointer[new_node] = NULL_POINTER    # it will be the last node
    if front_ptr == NULL_POINTER:       # queue was empty
        front_ptr = new_node
    else:
        pointer[end_ptr] = new_node     # old end now points to new node
    end_ptr = new_node

def leave_queue():
    global front_ptr, end_ptr, free_ptr
    if front_ptr == NULL_POINTER:
        return ""
    node = front_ptr
    front_ptr = pointer[node]
    if front_ptr == NULL_POINTER:
        end_ptr = NULL_POINTER          # queue is now empty
    pointer[node] = free_ptr
    free_ptr = node
    return data[node]

🕸️ 23.10 Graphs Figures 23.09–23.12

In computer science a graph is an ADT made of vertices (nodes) and edges. Graphs record relationships between things. Chapter 22 (Section 22.02) uses graphs in AI. Figure 23.09 is a simple graph showing a small part of the London Underground map from Chapter 12 (Figure 12.02).

**Figure 23.09**Graph showing part of the London Underground map

The vertices A to F are stations and the edges are train lines between them. You can take a train straight from B to D. To get from B to F you have to go via C or E. Two vertices joined by an edge are neighbours.

A labelled (weighted) graph has values on its edges. Here the weights show the time to travel between stations:

**Figure 23.10**Weighted graph showing travelling times between stations

Graphs can be directed or undirected (like Figure 23.10). Travel times may differ by direction, which a directed graph can show (Figure 23.11).

**Figure 23.11**Directed graph: each direction has its own travel time

Sometimes one direction is not available at all. If the line from B to D is blocked, the graph looks like Figure 23.12.

**Figure 23.12**Directed graph with the line from B to D blocked

You can use a graph to plan a journey. In Figure 23.12, to travel from C to D you can take C B A D (11 minutes) or C F E D (9 minutes). For the return journey you can use D B C (7 minutes).

🗺️ Lab: route planner on Figure 23.12

Type a route as letters, e.g. C F E D. The lab checks that each edge exists in that direction and adds up the minutes.

From To

The quickest-route search uses Dijkstra's algorithm. That goes beyond this chapter; Chapter 22 uses a similar idea.

Task 23.09 Draw the labelled edges for a directed graph of a road system where:

A to B is 2 km, and it is a one-way system
D to A is 1 km, and is one-way
B to D is 3 km and is one-way
B to C is 4 km
C to E is 7 km
D to E is 5 km.

**Task 23.09**Task 23.09: the five vertices to connect

The three one-way roads have a single arrow. B–C, C–E and D–E have arrowheads at both ends (or draw two arrows, each labelled with the same distance).

Implementing a graph

A graph can be stored as an adjacency matrix or an adjacency list.

An adjacency matrix records the relationship between every vertex and every other vertex. For an unweighted graph, 1 means an edge and 0 means no edge. For a weighted graph the weight replaces the 1, and the infinity symbol ∞ replaces the 0.

	A	B	C	D	E	F
A	0	1	0	1	0	0
B	1	0	1	1	1	0
C	0	1	0	0	0	1
D	1	1	0	0	1	0
E	0	1	0	1	0	1
F	0	0	1	0	1	0

Table 23.01 Adjacency matrix for Figure 23.09

	A	B	C	D	E	F
A	∞	3	∞	5	∞	∞
B	3	∞	3	∞	4	∞
C	∞	3	∞	∞	∞	2
D	5	4	∞	∞	2	∞
E	∞	4	∞	4	∞	2
F	∞	∞	3	∞	3	∞

Table 23.02 Adjacency matrix for Figure 23.12 (row = from, column = to)

An adjacency list records, for each vertex, only the vertices it is connected to. An entry is made only when there is an edge. For a weighted graph, the weight is stored alongside each connection.

	Connected to
A	B, D
B	A, C, D, E
C	B, F
D	A, B, E
E	B, D, F
F	C, E

Table 23.03 Adjacency list for Figure 23.09

	Connected to
A	B, 3; D, 5
B	A, 3; C, 3; E, 4
C	B, 3; F, 2
D	A, 5; B, 4; E, 2
E	B, 4; D, 4; F, 2
F	C, 3; E, 3

Table 23.04 Adjacency list for Figure 23.12

Which to choose? A matrix gives instant lookup of any edge but always needs n² cells, even when most are empty. A list stores only the edges that exist, so it suits sparse graphs, but checking one particular edge means scanning a vertex's list.

Task 23.10 Construct an adjacency matrix and an adjacency list to represent your graph from Task 23.09.

From \ to	A	B	C	D	E
A	∞	2	∞	∞	∞
B	∞	∞	4	3	∞
C	∞	4	∞	∞	7
D	1	∞	∞	∞	5
E	∞	∞	7	5	∞

	Connected to
A	B, 2
B	C, 4; D, 3
C	B, 4; E, 7
D	A, 1; E, 5
E	C, 7; D, 5

Notice the matrix is not symmetrical, because three roads are one-way.

#️⃣ 23.11 Hash tables Figures 23.13–23.15

To store records in an array and reach any record directly, you can use a hash table.

The idea is to calculate an address (the array index) from the record's key value, and store the record there. To find a record later, you calculate the address from the key again and go straight to it. Calculating an address from a key is called hashing.

It is very hard to find a hashing function that gives a unique address for every key. When two different keys hash to the same address, it is called a collision. There are several ways to handle collisions:

chaining: create a linked list for the collisions, with its start pointer at the hashed address
overflow areas: store every collision in a separate overflow area, known as "closed hashing"
neighbouring slots: do a linear search from the hashed address to find an empty slot, known as "open hashing".

Terminology warning. Many other textbooks use these names the other way round: they call the neighbouring-slot method "open addressing" or "closed hashing", and chaining "open hashing". In an exam, describe the method rather than relying on the name.

Worked Example 23.01: Calculating addresses in a hash table

We want to store customer records in a 1D array HashTable[0 : n]. Each customer has a unique customer ID, an integer from 10001 to 99999.

We need a hashing function whose results can reach every index of the array. The simplest one gives addresses from 0 to n:

FUNCTION Hash(Key) RETURNS INTEGER
    Address ← Key MOD (n + 1)
    RETURN Address
ENDFUNCTION

To illustrate, take n = 9. The hashing function becomes Index ← CustomerID MOD 10. We want to store records with IDs 45876, 32390, 95312, 64636 and 23467. The first three go straight into their slots (Figure 23.13).

**Figure 23.13**A hash table without collisions

The fourth key, 64636, also hashes to index 6. That slot is taken, so there is a collision. Storing the record there would overwrite the previous one. Instead, we store it in the next free slot (Figure 23.14).

**Figure 23.14**A hash table with a collision resolved by open hashing

The fifth key, 23467, hashes to index 7, which the previous record now occupies. Again we use the next free slot (Figure 23.15).

**Figure 23.15**A hash table with two collisions resolved by open hashing

When searching for a record, we have to allow for these out-of-place records. We know the record is not in the table when we reach an empty slot.

Below are algorithms to insert a record into a hash table and to search for one by its key. The hash table is a 1D array HashTable[0 : Max] OF Record, and each record has a unique key in the field Key.

Insert a record into a hash table

PROCEDURE Insert(NewRecord)
    Index ← Hash(NewRecord.Key)
    WHILE HashTable[Index] NOT empty DO
        Index ← Index + 1 // go to next slot to check if empty
        IF Index > Max // beyond table boundary?
          THEN // wrap around to beginning of table
            Index ← 0
        ENDIF
    ENDWHILE
    HashTable[Index] ← NewRecord
ENDPROCEDURE

Find a record in a hash table

FUNCTION FindRecord(SearchKey) RETURNS Record
    Index ← Hash(SearchKey)
    WHILE (HashTable[Index].Key <> SearchKey)
      AND (HashTable[Index] NOT empty) DO
        Index ← Index + 1 // go to next slot
        IF Index > Max // beyond table boundary?
          THEN // wrap around to beginning of table
            Index ← 0
        ENDIF
    ENDWHILE
    IF HashTable[Index] NOT empty // if record found
      THEN
        RETURN HashTable[Index] // return the record
    ENDIF
ENDFUNCTION

Two gaps to know about. If the table is full, Insert loops forever, and so does FindRecord when it searches for a missing key. A real version counts the slots it has checked and stops after Max + 1. Also, FindRecord returns nothing when the record is missing; a complete function should return a "not found" value.

🔬 Lab: hash table with open hashing

n = 9 Hash: Key MOD 10

📖 23.12 Dictionaries

A real-world dictionary is a collection of key–value pairs. The key is the term you look up to find its value. In an English–French dictionary, looking up the English word "book" gives the French "livre". A paper dictionary is organised in alphabetical order of keys.

A dictionary ADT in computer science is implemented with a hash table (Section 23.11), so a value can be looked up by direct access. Python, VB.NET and Java all have a built-in dictionary class.

Python

EnglishFrench = {} # empty dictionary
EnglishFrench["book"] = "livre" # add a key-value pair
EnglishFrench["pen"] = "stylo"
print(EnglishFrench["book"]) # access a value
# alternative method of setting up a dictionary
ComputingTerms = {"Boolean" : "can be TRUE or FALSE", "Bit" : "0 or 1"}
print(ComputingTerms["Bit"])

VB.NET

Dim EnglishFrench As New Dictionary(Of String, String)
EnglishFrench.Add("book", "livre")
EnglishFrench.Add("pen", "stylo")
Console.WriteLine(EnglishFrench.Item("book"))
Dim ComputingTerms As New Dictionary(Of String, String)
ComputingTerms.Add("Boolean", "can be TRUE or FALSE")
ComputingTerms.Add("Bit", "0 or 1")
Console.WriteLine(ComputingTerms.Item("Bit"))
Console.ReadLine()

Java

Java's Dictionary class is obsolete; use HashMap instead:

import java.util.Map;
import java.util.HashMap;
    Map<String, String> englishFrench = new HashMap<String, String>();
    englishFrench.put("book", "livre");
    englishFrench.put("pen", "stylo");
    System.out.println(englishFrench.get("book"));
    Map<String, String> computingTerms = new HashMap<String, String>();
    computingTerms.put("Boolean", "can be TRUE or FALSE");
    computingTerms.put("Bit", "0 or 1");
    System.out.println(computingTerms.get("Bit"));

These languages have many more built-in dictionary functions, which are beyond this book. What matters is understanding how a dictionary is implemented. This pseudocode creates a new one:

TYPE DictionaryEntry
    DECLARE Key   : STRING
    DECLARE Value : STRING
ENDTYPE
DECLARE EnglishFrench : ARRAY[0 : 999] OF DictionaryEntry  // empty dictionary

Task 23.11 Write pseudocode to insert a key–value pair into a dictionary, and to look up a value in a dictionary. Use the hashing function from Worked Example 23.01.

The keys here are strings, but Worked Example 23.01 hashes an integer with MOD. So first turn the string into an integer, here by adding up its character codes, then use MOD 1000 to get an index from 0 to 999 (n = 999). Each entry starts with Key ← "", which means "empty".

CONSTANT Max = 999

FUNCTION Hash(Key : STRING) RETURNS INTEGER
    DECLARE Total, i : INTEGER
    Total ← 0
    FOR i ← 1 TO LENGTH(Key)
        Total ← Total + ASC(MID(Key, i, 1))
    NEXT i
    RETURN Total MOD (Max + 1)
ENDFUNCTION

PROCEDURE InsertPair(NewKey : STRING, NewValue : STRING)
    DECLARE Index, Count : INTEGER
    Index ← Hash(NewKey)
    Count ← 0
    WHILE EnglishFrench[Index].Key <> "" AND EnglishFrench[Index].Key <> NewKey
          AND Count <= Max DO
        Index ← (Index + 1) MOD (Max + 1)    // next slot, wrapping round
        Count ← Count + 1
    ENDWHILE
    IF Count > Max
      THEN
        OUTPUT "Dictionary full"
      ELSE
        EnglishFrench[Index].Key ← NewKey       // same key again: value is replaced
        EnglishFrench[Index].Value ← NewValue
    ENDIF
ENDPROCEDURE

FUNCTION LookUp(SearchKey : STRING) RETURNS STRING
    DECLARE Index, Count : INTEGER
    Index ← Hash(SearchKey)
    Count ← 0
    WHILE EnglishFrench[Index].Key <> SearchKey AND EnglishFrench[Index].Key <> ""
          AND Count <= Max DO
        Index ← (Index + 1) MOD (Max + 1)
        Count ← Count + 1
    ENDWHILE
    IF EnglishFrench[Index].Key = SearchKey
      THEN
        RETURN EnglishFrench[Index].Value
      ELSE
        RETURN ""                              // key not in dictionary
    ENDIF
ENDFUNCTION

📈 23.13 Big O notation

A problem can usually be solved by more than one algorithm, and we want the one that uses time and memory efficiently. One way to compare efficiency is to describe the order of growth: how the running time (or memory) grows as the size of the input grows. Big O notation classifies algorithms this way. The letter O is used because the growth rate of a function is also called the "order of the function". The worst case is used when working out the order of growth for very large data sets.

Take the linear search from Chapter 13 (Worked Example 13.02). The worst case is when the item is the last one in the list. The longer the list, the more comparisons. Double the list and you double the comparisons. The order of growth is linear, written O(n), where n is the size of the data set.

Now the bubble sort, in its worst case:

Unsorted ← n - 1
FOR i ← 0 TO n - 2
    FOR j ← 0 TO Unsorted - 1
        IF MyList[j] > MyList[j + 1]
          THEN
            Temp ← MyList[j]
            MyList[j] ← MyList[j + 1]
            MyList[j + 1] ← Temp
        ENDIF
    NEXT j
    Unsorted ← Unsorted - 1
NEXT i

The basic operation is the comparison IF MyList[j] > MyList[j + 1].

n	Number of comparisons
1	0
2	1
3	3	= 1 + 2
4	6	= 1 + 2 + 3
5	10	= 1 + 2 + 3 + 4
6	15	= 1 + 2 + 3 + 4 + 5

Table 23.05 Number of comparisons in bubble sort

The total number of comparisons is the sum of the first (n − 1) whole numbers, which gives the formula ½ × n × (n − 1) = ½ × (n² − n). For very large n we can ignore everything except the largest term, which leaves n². So the order of growth is O(n²).

Now the binary search from Section 23.04. Each iteration halves the number of values left. That repeated halving gives a growth curve that rises steeply at first and then flattens out as the data set grows. This is O(log₂ n).

Order of growth	Example	Explanation
O(1)	`FUNCTION GetFirstItem(List : ARRAY)` `RETURN List[1]`	The time does not change, whatever the size of the data set.
O(n)	Linear search Bubble sort performed on an already sorted list	Linear growth.
O(log₂ n)	Binary search	The total time increases as the data set grows, but each comparison halves the data set. So the time increases by smaller and smaller amounts and approaches constant time.
O(n²)	Bubble sort Insertion sort	Polynomial growth. Common with algorithms that have nested iterations over the data set.
O(n³)		Polynomial growth. Deeper nested iterations give O(n³), O(n⁴), …
O(2ⁿ)	Recursive calculation of Fibonacci numbers	Exponential growth.

Table 23.06 Order of growth (time complexity) for a data set of size n

Note on the bubble-sort-on-sorted-list row. That O(n) only holds for the version with a swapped flag (Task 23.02). The fixed-pass version above always makes ½(n² − n) comparisons, even on a sorted list.

Space complexity is the amount of memory needed as the number of values n in the data set grows. The ADT operations in this chapter have space complexity O(n): they need only the space for the data itself. Bubble sort and insertion sort have space complexity O(1): they need no extra memory to sort a larger list.

🔬 Lab: how fast does each order grow?

Drag n. Bars use a logarithmic scale, so each grid line is 10 times the one below.

n = 16

🎮 Name the order of growth

Reflection point: List the standard algorithms you have met in this chapter. Can you give the essential features of each?

Algorithm	Essential features	Time
Linear search	Check each item in turn; works on unordered data	O(n)
Binary search	Ordered data only; check the middle, discard half	O(log₂ n)
Bubble sort	Swap adjacent pairs; largest bubbles to the end each pass; flag stops early	O(n²)
Insertion sort	Take the next item and slide it back into the sorted part	O(n²)
Linked list insert/find/delete	Follow pointers from the start; only pointers change; free list holds spare nodes	O(n)
Binary tree insert/find	Go left if smaller, right if larger, from the root	O(log₂ n) if balanced, O(n) worst
Stack push/pop	LIFO; one top pointer	O(1)
Queue add/remove	FIFO; front and end pointers with wrap-round	O(1)
Hash table insert/find	Hash the key to an address; on a collision try the next slot	O(1) typical

📌 Summary

Standard algorithms include bubble sort, insertion sort, linear search and binary search.
Abstract data types (ADTs) include stacks, queues, linked lists, binary trees, hash tables, dictionaries and graphs.
The basic operations on an ADT are creating it and inserting, finding or deleting an element.
The time taken and the space used can be measured with Big O notation.

🃏 Key-term flashcards

Tap a card to flip it.

✅ Quick quiz

📝 Exam-style questions

Write your answer first, then open the model answer. These are my mark-scheme-style points, not official mark schemes.

FUNCTION FindName(s : STRING) RETURNS INTEGER
    Index ← -1
    First ← 0
    Last ← 50
    WHILE (Last >= First) AND (Index = -1) DO
        Middle ← (First + Last) DIV 2
        IF Names[Middle] = s
          THEN
            Index ← Middle
          ELSE
            IF Names[Middle] > s
              THEN
                Last ← Middle - 1
              ELSE
                First ← Middle + 1
            ENDIF
        ENDIF
    ENDWHILE
    RETURN Index        // this line is needed too
ENDFUNCTION

1 mark: Index = -1 (or NOT Found) in the loop condition.
1 mark: Names[Middle] > s.
1 mark: First ← Middle + 1.

Book misprint. The question prints Last ← Middle + 1 in the THEN branch. When the middle name is too big, the upper boundary must move below Middle, so it should be Last ← Middle - 1. With + 1 the search can loop forever. The printed function also has no RETURN line.

not sorted (not in order).

(i) The index (position) of the name in the array, from 0 to 50.

(ii) −1.

Node	Data	Pointer	Labels
1	Apple	→ node 2	← FrontOfQueue
2	Pear	→ node 3
3	Banana	Ø (null)	← EndOfQueue
4		→ node 5	← StartOfFreeList
5		Ø (null)

(i) Marks for: data in the right order; FrontOfQueue pointing at Apple; EndOfQueue pointing at Banana; Apple → Pear → Banana pointers; a null pointer in Banana's node.

(ii) StartOfFreeList points to node 4; node 4 points to node 5; node 5 holds the null pointer.

NULL_POINTER = -1

class Node:                         # (i)
    def __init__(self):
        self.data = ""              # data field: string
        self.pointer = NULL_POINTER # pointer field: integer

# (ii)
queue = [Node() for _ in range(50)]     # 50 records, indexes 0..49
for index in range(49):
    queue[index].pointer = index + 1    # link every node into the free list
queue[49].pointer = NULL_POINTER        # last free node
front_of_queue = NULL_POINTER           # queue is empty
end_of_queue = NULL_POINTER
start_of_free_list = 0

Pseudocode equivalent for (i): TYPE Node / DECLARE Data : STRING / DECLARE Pointer : INTEGER / ENDTYPE.

Identifier	Data type	Description
NullPointer	INTEGER	Constant set to −1
Queue	ARRAY[0 : 49] OF Node	Array to store queue data
NewItem	STRING	Value to be added
StartOfFreeList	INTEGER	Pointer to next free node in array
FrontOfQueue	INTEGER	Pointer to first node in queue
EndOfQueue	INTEGER	Pointer to last node in queue
NewNodePointer	INTEGER	Pointer to node to be added

PROCEDURE JoinQueue(NewItem : STRING)
    // Report error if no free nodes remaining
    IF StartOfFreeList = NullPointer
      THEN
        Report Error
      ELSE
        // new data item placed in node at start of free list
        NewNodePointer ← StartOfFreeList
        Queue[NewNodePointer].Data ← NewItem
        // adjust free list pointer
        StartOfFreeList ← Queue[NewNodePointer].Pointer
        Queue[NewNodePointer].Pointer ← NullPointer
        // if first item in queue then adjust front of queue pointer
        IF FrontOfQueue = NullPointer
          THEN
            FrontOfQueue ← NewNodePointer
            EndOfQueue ← NewNodePointer
        ENDIF
        // new node is new end of queue
        Queue[EndOfQueue].Pointer ← NewNodePointer
        EndOfQueue ← NewNodePointer
    ENDIF
ENDPROCEDURE

A flaw in the printed template. Filled in as above, the first node to join ends up pointing at itself, because the last two lines also run for the first item. That self-pointer is harmless here, since the next JoinQueue overwrites it. A cleaner design puts Queue[EndOfQueue].Pointer ← NewNodePointer in an ELSE branch. Some answers instead leave EndOfQueue out of the THEN branch; that version is wrong for an empty queue, because Queue[-1] would be written.

# (a)
MAX_WORDS = 500
word_list = [""] * MAX_WORDS

# (b)
def output_list():
    for index in range(MAX_WORDS):
        if word_list[index] != "":          # skip unused elements
            print(word_list[index])

# (c)
def load_words():
    filename = input("Enter the filename: ")
    try:
        with open(filename, "r") as file:
            index = 0
            for line in file:
                word = line.strip()
                if word == "":
                    continue
                if index >= MAX_WORDS:
                    print("Error: the array is full; remaining words not loaded")
                    break
                word_list[index] = word
                index = index + 1
    except FileNotFoundError:
        print("Error: the file", filename, "does not exist")

# (d)
def sort_words():
    count = 0                               # how many non-empty elements?
    while count < MAX_WORDS and word_list[count] != "":
        count = count + 1
    unsorted = count - 1
    swapped = True
    while swapped and unsorted > 0:
        swapped = False
        for j in range(unsorted):
            if word_list[j].lower() > word_list[j + 1].lower():
                word_list[j], word_list[j + 1] = word_list[j + 1], word_list[j]
                swapped = True
        unsorted = unsorted - 1

# (e)
load_words()
output_list()
sort_words()
print("--- sorted ---")
output_list()

(f) Run once with a filename that does not exist: the screenshot should show the error message and no crash. Run again with a file of 20 words in random order: the screenshot should show the unsorted list, then the same 20 words in alphabetical order.

Comparing .lower() versions means "apple" and "Apple" sort together; without it, every capitalised word sorts before every lowercase one.

Guru Jazzy · Cambridge AS & A Level Computer Science · Chapter 23 Algorithms · Figures from the Cambridge coursebook (Langfield & Duddell) · Model answers are my own

	A	B	C	D	E	F
A	∞	3	∞	5	∞	∞
B	3	∞	3	∞	4	∞
C	∞	3	∞	∞	∞	2
D	5	4	∞	∞	2	∞
E	∞	4	∞	4	∞	2
F	∞	∞	3	∞	3	∞

From \ to	A	B	C	D	E
A	∞	2	∞	∞	∞
B	∞	∞	4	3	∞
C	∞	4	∞	∞	7
D	1	∞	∞	∞	5
E	∞	∞	7	5	∞

	A	B	C	D	E	F
A	∞	3	∞	5	∞	∞
B	3	∞	3	∞	4	∞
C	∞	3	∞	∞	∞	2
D	5	4	∞	∞	2	∞
E	∞	4	∞	4	∞	2
F	∞	∞	3	∞	3	∞

From \ to	A	B	C	D	E
A	∞	2	∞	∞	∞
B	∞	∞	4	3	∞
C	∞	4	∞	∞	7
D	1	∞	∞	∞	5
E	∞	∞	7	5	∞

	A	B	C	D	E	F
A	∞	3	∞	5	∞	∞
B	3	∞	3	∞	4	∞
C	∞	3	∞	∞	∞	2
D	5	4	∞	∞	2	∞
E	∞	4	∞	4	∞	2
F	∞	∞	3	∞	3	∞

From \ to	A	B	C	D	E
A	∞	2	∞	∞	∞
B	∞	∞	4	3	∞
C	∞	4	∞	∞	7
D	1	∞	∞	∞	5
E	∞	∞	7	5	∞