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
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
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
- 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 we add D as a left child from E
Store the binary tree in an array of records.
binary tree algorithm
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.