ALevel-CS Chapter 23 Algorithms

23.01 Linear search

23.02 Bubble sort

23.03 Insertion sort

Insertion sort

sorted part and unsorted part

pseudocode
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

23.04 Binary Search

Binary Search

20210313090428873

20210312165413832

Binary search: repeated checking of the middle item in an ordered search list and discarding the half of the list which does not contain the search item

Pseudocode
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

23.05 Abstract Data Types (ADTS)

23.06 Linked List

Linked List

linklist

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 = StartPointer 
                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

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

23.07 Binary trees

Binary Trees

Nodes are added to an ordered binary tree\ (Structure English):

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.
Example :: add a new node with data value D to the binary tree
  1. Start at the root node.
  2. D is smaller than F, so turn left.
  3. D is greater than C, so turn right.
  4. D is smaller than E, so turn left.
  5. There is no branch going left from E, so we add D as a left child from E

Store the binary tree in an array of records.

binary tree algorithm

binary_tree

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

23.08 Stacks

Stacks

A stack can be implemented using a 1D array.

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[1 : MaxStackSize – 1] OF STRING

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

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[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

23.09 Queues

Queues

A queue can be implemented using a 1D array.

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

23.10 Graphs

Graphs

Graphic

Weighted graphic

Directed graph

In Computer Science a graph is an ADT consisting of vertices (nodes) and edges.

A labelled(Weighted) graph has edges with values representing something.

Graphs can be directed or undirected.

To implement a graph, we can use an adjacency matrix or an adjacency list

For an unweighted graph, a 1 represents an edge, a 0 no edge. When weights are to be recorded, the weight replaces the 1. Instead of a 0, we use the infinity symbol ∞.

An adjacency list stores the relationship between every vertex to all relevant vertices. An entry is made only when there is an edge between two vertices.

23.11 Hash tables

Hash tables

The idea behind a hash table is that we calculate an address (the array index) from the key value of the record and store the record at this address.

Calculating an address from a key is called ‘hashing’.

Finding a hashing function that will give a unique address from a unique key value is very difficult. If two different key values hash to the same address this is called a ‘collision’. There are different ways to handle collisions::

  • chaining:: create a linked list for collisions with start pointer at the hashed address
  • using overflow areas:: all collisions are stored in a separate overflow area, known as ‘closed hashing’
  • using neighbouring slots:: perform a linear search from the hashed address to find an empty slot, known as ‘open hashing’.

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

23.12 Dictionaries

Dictionaries

A real-world dictionary is a collection of key–value pairs.

The key is the term you use to look up the required value.

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

23.13 Big O notation

A problem can be solved in different ways, with different algorithms.

Clearly, we want to use time and memory efficiently. A way of comparing the efficiency of algorithms has been devised using order of growth as a function of the size of the input.

Big O notation is used to classify algorithms according to how their running time (or space requirements) grows as the input size grows. The letter O is used because the growth rate of a function is also referred to as ‘order of the function’. The worst-case scenario is used when calculating the order of growth for very large data sets.

辅助阅读