Student Workbook

Your Name: Class:

© Nichola Wilkin Ltd 2020 Page 1

www.nicholawilkin.com
 Knowledge Checklist
Before you start, please tick the areas you are already confident in.
Once you have worked through ALL of this workbook (including
those areas you are already familiar with) go through the checklist
again and tick the areas you now feel confident in and which areas
you still need to work on.

I am confident
I am confident now I have I still need to
before I start completed work on this
this workbook this workbook area

Principles of computational thinking:

Abstraction

Decomposition

Algorithmic thinking
Identify the inputs, processes and
outputs for a problem
Structure diagrams
Create, interpret, correct, complete
and refine algorithms using:
Pseudocode

Flowcharts
Reference language/high-level
programming language
Identify common errors

Trace tables

Standard searching algorithms:

Binary search

Linear search

Standard sorting algorithms:

Bubble sort

Merge sort

Insertion sort

© Nichola Wilkin Ltd 2020 Page 2

www.nicholawilkin.com
 Table of Contents
Knowledge Checklist ............................................................................................... 2
Computational thinking .......................................................................................... 5
What is an algorithm? .......................................................................................... 5
Computer programs and algorithms ................................................................. 5
Decomposition ..................................................................................................... 7
Abstraction............................................................................................................ 8
Algorithmic thinking............................................................................................ 11
Identifying the inputs, processes and outputs for a problem ............................ 12
Inputs ................................................................................................................... 12
Processes ............................................................................................................. 13
Outputs ................................................................................................................ 13
Structure Diagrams ................................................................................................ 14
Basic Pseudocode ................................................................................................. 16
Recap programming basics ............................................................................. 16
What is an expression?....................................................................................... 17
Camel Case ........................................................................................................ 17
Setting the value of an expression ................................................................... 17
Arithmetic Operations........................................................................................ 18
Relational Operators .......................................................................................... 19
Boolean Operators ............................................................................................. 19
Input and Output ............................................................................................... 21
Iteration ............................................................................................................... 21
Selection.............................................................................................................. 25
Nesting statements ............................................................................................. 27
Switch case ......................................................................................................... 28
Dealing with strings ............................................................................................. 30
Arrays ................................................................................................................... 32
External files ......................................................................................................... 34
Sub programs ...................................................................................................... 35
Flowcharts ............................................................................................................... 37
Flowchart symbols .............................................................................................. 38
Drawing loops in flowcharts .............................................................................. 40
Understanding flowcharts ................................................................................. 43
Showing sub programs in flowcharts ................................................................ 45

© Nichola Wilkin Ltd 2020 Page 3

www.nicholawilkin.com
High-level programming languages .................................................................... 47
Refining programs .............................................................................................. 48
Identify common errors ......................................................................................... 49
What are the different types of error?.............................................................. 49
Syntax error ......................................................................................................... 49
Run-time error ..................................................................................................... 49
Logic errors .......................................................................................................... 51
Trace Tables............................................................................................................ 52
How do you create a trace table? .................................................................. 52
Creating the trace table ................................................................................... 52
Filling in the trace table ..................................................................................... 53
Standard searching algorithms ............................................................................ 58
Linear search ...................................................................................................... 58
Binary search ...................................................................................................... 60
Standard sorting algorithms .................................................................................. 64
Bubble sort .......................................................................................................... 64
Merge sort ........................................................................................................... 68
Insertion sort ........................................................................................................ 73
Number Cards ........................................................................................................ 78

© Nichola Wilkin Ltd 2020 Page 4

www.nicholawilkin.com
 Computational thinking
Task 1: Get two pieces of paper and on one of them draw an
animal. It can be any animal you want, real or imaginary. Add
some details such as fur, scales or a pattern to make it look more
interesting. We will be using this drawing later on.

What is an algorithm?

An algorithm is a
sequence of instructions
that can be followed to
complete a task

Computers, robots and most modern

technology need to be programmed and
learning how to write algorithms is an
important part of computing. Algorithms
can take many forms including simple
written instructions, pseudocode and
flowcharts. We are going to be looking at
how to write pseudocode and flowcharts a
little later.

Computer programs and

algorithms
Computer programs are not classed as
algorithms as they are implementations of
algorithms. In other words, the computer
program is based on an algorithm but it is
not an algorithm itself. Think of the
algorithm as the plans and the computer
program as the final product. The
algorithm is not simply writing out the
program, it is created during the planning
stage and therefore should be developed
first, before the computer program is
written. When you write complex
computer programs it may help you to
identify the algorithms and this book will
help you do that.

© Nichola Wilkin Ltd 2020 Page 5

www.nicholawilkin.com
Remember the animal you drew earlier; let’s see if the outcome is the same
when you follow this algorithm.

Task 2: Hide the animal you drew earlier so you can no longer
see it and get your other piece of paper. Without looking at the
previous animal you drew, follow these steps to try to draw the
same picture again:

Step 1 - Draw the eyes first (but do not draw the outline of the
head). If your animal does not have eyes draw another small
feature but not the outside outline of the animal

Step 2 - Draw the tail or a single leg. If your animal has neither of
these things, draw another feature of your animal that is not
directly connected to the section you drew before

Step 3 - Turn the paper 90o clockwise and draw the rest of the
animal WITH YOUR EYES CLOSED!

Did you manage to draw the animal exactly the same as the first attempt?
What was different this time?

The instructions you were following were not the same as before; they didn’t
make sense and were over complicated. If the instructions for how to do
something are not in a logical clear order, the end result will not be as you
expect. That is what good algorithms do. They set out the sequence of steps
to be completed in a logical order to achieve the desired outcome.

© Nichola Wilkin Ltd 2020 Page 6

www.nicholawilkin.com
Decomposition
Look at this zombie. It is certainly
“decomposing”, but what does
decomposition mean?

To write an algorithm there are a few steps

that are necessary and the first one is
“decomposing the problem”. This does not
mean everything turns to a messy mush, as our
zombie will eventually become, but rather it
means breaking a larger problem into smaller
ones.

Decomposition = Breaking a larger problem into smaller

manageable tasks

Task 3: Use the space below to write instructions to tell

somebody how to brush their teeth

Look at the instructions you wrote. Are they written in one long paragraph or
using separate short statements using bullet points or numbers or did you
create something else altogether such as a diagram or storyboard splitting
the instructions into small individual tasks? Which would you prefer to use, a
long paragraph or something split into smaller chunks? If you did not know
how to brush your teeth and were going to follow these instructions would a
single long paragraph or smaller chunks help you keep track of what you
have done and what you need to do next?

Most people would write the instructions for brushing your teeth by splitting
the larger complex task into smaller sections (i.e. 1 - Put toothpaste on the
toothbrush 2 - Put toothbrush in your mouth with the bristles against your teeth
© Nichola Wilkin Ltd 2020 Page 7
www.nicholawilkin.com
etc). Rather than one long paragraph we automatically break down large
complicated tasks into smaller manageable chunks. For most of us it is
human nature to do this without thinking about it and is the first step to writing
a good algorithm.

Abstraction
After you have broken down a larger problem into smaller steps the next
stage is “abstraction”.

Task 4: Think of a contacts list or an address book. Using the

space below write down the things that you think are essential
to have in the “Have to have” column and then write down the
things you think would like but are not essential to have in the
“Nice to have” column
Have to have Nice to have

Look back over your list and move things between the columns. Change
your mind if you want before reading on.

In fact, you only have to have three options that are absolutely essential:
name or other way of identifying them, method of contact (phone, email
etc) and contact details. Everything else is nice to have i.e. date of birth,
secondary method of contact etc.

Abstraction = The process of removing UNNECESSARY

detail from a problem

© Nichola Wilkin Ltd 2020 Page 8

www.nicholawilkin.com
Imagine we wanted to draw a Christmas tree. We would need to decide on
how much detail we want to include.

Very Least
detailed detailed

Ask yourself “How little detail can I get away with but still make it obvious it is
a Christmas tree?” It may be argued that the very simple tree on the far right
is the least likely to be easily identifiable as a Christmas tree and may possibly
be mistaken for just a triangle or representing something else altogether.
When abstracting a problem, you need to get rid of anything that is not
needed BUT you do need to still include specific details that your solutions
require so don’t get rid of anything that is actually essential. This is a skill that
can be quite hard as the line between “nice to have” and “have to have”
can be interpreted differently by different people. If you are working as part
of a team on a large project, you need to communicate clearly with each
other, so everybody agrees on what is classed as essential.

Look back at the instructions you wrote for brushing your teeth. You probably
automatically “abstracted” the problem and got rid of unnecessary
information such as the colour of the toothbrush or what you wear, as these
are unnecessary details. You may have also got rid of unnecessary words
and kept the instructions brief and punchy.

© Nichola Wilkin Ltd 2020 Page 9

www.nicholawilkin.com
 Task 5: Describe the features that the following things HAVE to
have:

Passenger
Aeroplane

Fish

An app to
test pupils
on their
times
tables

Look again at the things you originally outlined as HAVE to have and see if
you have changed your mind and some of them are now classed as NICE to
have. Delete any that you now think could be classed as nice to have.

Some things will be classed as essential that you may think are only nice to
have but are required to be included to follow the law. For instance, the UK
Civil Aviation Authority (CAA) states that:

• Every individual aircraft has a “certificate of airworthiness” which is

renewed every few years
• There must be a safety information card provided near every
passenger seat
• Young children and infants who are accompanied by adults should
ideally be seated in the same seat row as the adult. Where this is not
possible, children should be separated by no more than one seat row
from accompanying adults.

There are many other rules the CAA stipulates but this gives you an idea of
some of the things they cover. There can be lots of regulations that you
would need to be aware of from lots of different authorities which are classed
as essential. For instance, if you were developing software to allocate seats
on an airplane you would certainly need to
be aware of the child seating requirements
from the CAA and take that into
consideration when developing your
algorithm.

© Nichola Wilkin Ltd 2020 Page 10

www.nicholawilkin.com
Algorithmic thinking
Algorithmic
We all learn the steps for finding the difference
between two numbers in primary school.
thinking = a
way of defining
Step 1: Find the largest of the two numbers the steps
Step 2: Take the smaller number away from the larger required to
number, the answer you are left with is the reach a
difference. solution
If we (or a computer) follow the same steps we can
find the difference between any two numbers. We don’t need to work out
how to find the difference between two numbers every time we are given
different numbers to work with.

The power of algorithmic thinking is that it allows solutions to be automated.

Task 6: Complete this crossword

ACROSS
2 The order your algorithm follows
4 We use this to filter out the details we do not need to solve our problem
5 This helps us by breaking down complex problems into more manageable
parts
DOWN
1 A written outline of how to perform a procedure
3 A sequence of instructions or a set of rules that are followed to complete a
task

© Nichola Wilkin Ltd 2020 Page 11

www.nicholawilkin.com
 Identifying the inputs, processes
and outputs for a problem
One of the first steps in planning an effective algorithm is to identify the
inputs, processes and outputs.

Inputs
Inputs are the data the user will need to input into the algorithm in order for it
to work correctly.

Imagine you have been given the task of creating a simple

program that will ask the user to input their details and it will work
out the delivery costs depending on where the items ordered will
be posted.

Task 7: Write a list of the data that user will need to input into the
system using a suitable label that will make sense later on and
also specify the most suitable data type that can be used (i.e.
string, integer, floating point, Boolean, date etc.). You do not
need to fill in all the rows in the following table.
Data label Data type

© Nichola Wilkin Ltd 2020 Page 12

www.nicholawilkin.com
Processes
The processes are the calculations or actions that the algorithm will need to
perform using those inputs.

Task 8: Using the inputs you identified in task 7, write down any
processes that need to be performed. You could include
processes which identify the validation that will need to be
carried out, any calculations that will be made (you can make
assumptions about delivery cost etc.) or how that data will be
saved. Describe a different process in each of the boxes below:

Outputs
You also need to consider the outputs that will be displayed to the user. This
can include messages to tell the user if they have done something wrong
(error messages), messages to tell them if the process has been a success,
and information about how much the delivery cost will be.

Task 9: Using the inputs and processes you identified in task 6

and 7, write down 3 outputs that may be displayed to the user
and explain when your messages will be displayed.
Output message When will this be displayed?

© Nichola Wilkin Ltd 2020 Page 13

www.nicholawilkin.com
 Structure Diagrams
Structure diagrams are great for helping to decompose a problem into
smaller more manageable sections.

Here are a few structure diagrams to help you see how to create them.
Structure diagrams are read from the top down and from left to right.

There are 4 symbols you need to be aware of:

Let’s have a look at how these are put together into a structure diagram.

Using iteration

This will ask the user to input 3 numbers, add the to a total and then display
the total.

© Nichola Wilkin Ltd 2020 Page 14

www.nicholawilkin.com
Selection

This program will ask the user to input a number, if that number is even it will
save it to a text file, otherwise it will display an error message.

Subprograms

This is the main program which contains two subprograms

This is the “Validate email address” sub program that will check to see if the
email address contains a @ symbol and also if it ends with a recognised
ending (i.e. .com, .co.uk etc)

© Nichola Wilkin Ltd 2020 Page 15

www.nicholawilkin.com
 Basic Pseudocode
Pseudocode (sometimes written as pseudo-code) is a generic language
used to help write algorithms in the planning stages of writing computer
programs. It is not a specific programming language and there are no set
rules but you must be consistent and the meaning should be clear.

The pseudocode we will be looking at in this book is particular to the OCR

GCSE (9-1) Computer Science (J276). However, you should also be aware
that pseudocode is not specific to any standard conventions and as long as
candidates are consistent throughout their algorithm and the meaning is
clear then any form of pseudocode is acceptable for examinations and
programming projects.

Recap programming basics

Task 10: Write a description for programming terminology
that we will be using in this workbook. If you are unsure
about the meaning of any of the terms do some further
research and find out before continuing to the next section

Variable

Constant

Integer

String

Boolean
value

Sub
program

© Nichola Wilkin Ltd 2020 Page 16

www.nicholawilkin.com
What is an expression?
An expression is a variable or constant that can be stored
as an integer, string, Boolean or floating point* data type

* A “floating point” data type can be any positive or negative number and
includes decimal places.

Camel Case
Camel case is a way of naming variables and constants. The first word
should remain lowercase but if there is more than one word that makes up
the name each subsequent word should start with a capital letter and the
words should be joined together with no spaces. Therefore “my age” would
become “myAge”.

Setting the value of an expression

• If it is a variable (i.e. the value can change) this
should be named using camel case
• If it is a global variable (i.e. the value is accessible
throughout the algorithm including sub programs
which we will be looking at later) it should have the
word global before it
• If it is a constant (i.e. the value will not change) this
should have the word const before it.

Define the expression first (i.e. give it a name) then use the = and the value to
assign the value after the = to that variable or constant.

Example Description

num = 3 num is a variable which has been

assigned the value 3

num is a global variable and can

global num = 3 be used in sub-routines and has
been assigned the value 3
num is a constant which has been
const num = 3
assigned the value 3 and this will
not change throughout the
algorithm

© Nichola Wilkin Ltd 2020 Page 17

www.nicholawilkin.com
 Task 11: Without looking back at the previous page, what
do the following expressions mean?

a = 3

global b = a + 1

const Pi = 3.141

Arithmetic Operations
Operator Description Example Answer
+ Addition 2+4 6
- Subtraction 5-1 4
* Multiplication 2*10 20
/ Division 12/4 3
DIV Whole Number Division 10 DIV 3 3
MOD Modulus (finds the remainder after 10 MOD 3 1
a whole number division)
^ Exponentiation (to the power of) 3^4 81

The above table outlines all the standard arithmetic operators that can be
used in pseudocode. Brackets are used to define the order of calculations.
For instance 5+2*10 is very different to (5+2)*10. The first would give the
answer 25 (it would multiply the 2 by the 10 first and then add the 5) but the
second statement would give the answer 70 (it would add the 5 and the 2
first and then multiply that by 10).

Task 12: Read the descriptions and write the required

expressions using pseudocode.

Add 100 to a variable called “a”,

multiply this total by 12 and save this
in another variable called “num”.
Take a constant called “num” and
perform a whole number division
where it is divided by 5 and store this
as a variable called “new”. Store
the remainder in another variable
called “rem”.

© Nichola Wilkin Ltd 2020 Page 18

www.nicholawilkin.com
Relational Operators
Operator Description Example

< Less than 2 < 3

> Greater than 50 > 20

== Equal to (10/2)== 5

Not equal to (Please note: this

!= (10/2)!= 3
can also be written as ≠ or <>)
Less than or equal to (Please
<= note: this can also be written as 2 <= 3
≤)
Greater than or equal to
>= (Please note: this can also be 5 >= 1
written as ≥)

Boolean Operators
Operator Description Example

All conditions must be met to (x >= 10) and (x <= 20)

and
be classed as true.
Only one of the conditions
or must be met to be classed as (x >= 10) or (y > 100)
true.
None of the conditions must be not (x == 10)
not
met to be classed as true.

© Nichola Wilkin Ltd 2020 Page 19

www.nicholawilkin.com
 Task 13: Read the statements and decide if they are true or
false. Place a tick in the relevant column.

Statement True False

4 < 6

4.1 > 4

5 <= 3

(22 DIV 5) == 5

10 != 20

(4 < 6) and (5 < 10)

((27 + 3) <= 30) or (50 < 20)

not (10 / 2 == 6)

not ((10 MOD 3) == 1)

((55 DIV 10) <= 5) and (55 MOD 10) == 5)

(3 < 10) and (10 > 8) and (8 > 5)

(47 * 2) >= 100 or ((83 MOD 2) == 1

((3 >= 3) and (5 != 4)) or (100 >= 50)

(5 > 3) and ((103 DIV 10) == 10)

37 != ((24 + 13) or (5 <= 3))

(37 == (24 + 13) and (NOT (5 <= 3))

(not (16 DIV 5) == 2)) and (16 DIV 5 == 1)

© Nichola Wilkin Ltd 2020 Page 20

www.nicholawilkin.com
Input and Output
These are two of the most common pieces of pseudocode you will use. Both
examples use a variable called “name”.

Action Pseudocode Description

This will ask the user
to input their name
Input name = input(“What is your name? ”) (the message in
brackets is the
prompt to the user)
This will output the
Output print(name) value of the variable
(variable)
name
This will output the
Output print(“Hello”) value of the string
(string)
“hello”

Iteration Iteration is another

There are two types of iteration:
name for loops

• Count-controlled iteration: this uses a “For”

loop to count how many times it should complete the loop. With this type of
loop the number of times it will be repeated is defined at the beginning of the
loop.
• Condition-controlled iteration: this includes a “Do…until” loop which will
repeat the statements until the condition is true and a “While” loop which will
repeat the loop as long as the condition is true. With the “Do…until” and
“While” loops the number of times it will be repeated will vary depending on if
the condition is met or not.
Here is an example of a count-controlled loop:
The print line is indented
for a = 1 to 3 as it is inside the For loop
print(a) and will be repeated.
next a

What do you think the output will be for this loop? The output will be 1, 2, 3.
At the end of the loop it uses the line “next a” to repeat the loop.

© Nichola Wilkin Ltd 2020 Page 21

www.nicholawilkin.com
 Task 14: Write a loop which will output the numbers from 10
to 1

What do you think this pseudocode will do?

for a = 2 to 10 step 2
print(a)
next a

It will produce the output 2, 4, 6, 8, 10 as it is counting in 2’s.

Here is an example of a conditioned controlled loop. What will it do?

a = 1
do
print(a)
a = a + 1
until a == 4

It sets a to 1 and then starts the loop. It outputs a

and then adds 1 to it and it will keep repeating
this loop until a equals 4, when it will end the loop.
The output will be 1, 2, 3.
a = 15
while a >= 10
print(a)
a = a - 1
endwhile

What will this pseudocode do? It sets a to 15 and

then starts the loop. It will check that a is greater
than or equal to 10. If it is, it will display the output
of a and then subtract 1 from a. It will keep doing
this as long as a is greater than or equal to 10,
then it will stop. This will produce the output 15, 14,
13, 12, 11, 10 and then stop.

© Nichola Wilkin Ltd 2020 Page 22

www.nicholawilkin.com
The main difference between a DO…UNTIL loop and a WHILE loop is when
the condition is checked.

Do…until Loop While Loop

a = 1 a = 15
do while a >= 10
print(a) print(a)
a = a + 1 a = a - 1
until a == 4 endwhile

The do…until loop checks if the condition has been met at the end of the
loop (i.e. it keeps looping UNTIL it meets that condition) but the while loop
checks if the condition has been met at the start of the loop ( i.e. it will loop
AS LONG AS it meets that condition).

What will this pseudocode do?

total = 0
while total <= 10
num = input(“Enter number”)
total = total + num
print(total)
endwhile

It will set the total to 0. As long as the total is less than or equal to 10 it will ask
the user to input a number and add this to the total. It will then display the
total and keep repeating the loop until the total is over 10 when it will stop
the loop.

What will this pseudocode do?

again = “yes”
total = 0
do
num = input(“Enter number”)
total = total + num
again = input(“Do you want to go again?”)
until again == “no”
print(total)

It will set a variable called again to “yes” and a total to 0. It will start a loop
that asks the user to enter a number and add that to the total. It will ask the
user if they want to go again and will keep repeating the loop until the user
enters no when asked if they want to repeat it again. Only once the loop is
stopped will it display the total.

© Nichola Wilkin Ltd 2020 Page 23

www.nicholawilkin.com
 Task 15: Write some pseudocode for each of the scenarios
given
1. Keep asking the user
to enter a number.
As long as that
number is under 10
ask again but as soon
as they enter a
number that is 10 or
above, stop asking.

2. Ask the user to enter

a day of the week.
Output that day of
the week three times
using a loop.

3. Ask the user to input a

number. As long as
they keep inputting
numbers that are
getting larger than
the previous one they
entered they should
keep going, otherwise
it should stop the
loop.

© Nichola Wilkin Ltd 2020 Page 24

www.nicholawilkin.com
Selection

Selection algorithms allow a decision to be made to

determine the most appropriate route through a set of
instructions
Selection algorithms use if statements The three variations you should be
aware of are:

• Basic if statement – this has one condition and one possible outcome if that
condition is true, otherwise it will do nothing.
• If…else – This has one condition and two possible outcomes. The first
outcome is if that condition is true and the second outcome is what it does if
that condition is not true.
• Else…if – this allows you to add additional conditions, so if the first condition is
not true you can test out alternative conditions.

Name Example Description

Basic If num = input(“Enter a number”) It will ask the user to input a
if (num MOD 2) == 0 then number. That number is
print(“even”)
then used in a whole
endif
number division by 2 and if
that remainder is equal to 0
(i.e. it is an even number) it
will output the message
“even”.
If…else num = input(“Enter a number”) It will ask the user to input a
if (num MOD 2) == 0 then number. If the number is an
print(“even”)
even number, it will output
else
print(“odd”) the message “even”,
endif otherwise it will output the
message “odd”.
Else…if num = input(“Enter a number”) It will ask the user to input a
if num < 10 then number. If the number is
print(“too low”)
under 10 it will display the
else if num > 20 then
print(“too high”) message “too low”, if the
else number is above 20 it will
print(“thank you”) display the message “too
endif high”. However, if neither
of these two conditions are
true (i.e. it is not under 10
and not over 20) it will
display the message “thank
you”.

© Nichola Wilkin Ltd 2020 Page 25

www.nicholawilkin.com
 Task 16: Write some pseudocode for each of the scenarios
given
1. Ask the user to enter
their age. If they are
under 18, display the
output “You are a
child”, otherwise
display the output
“You are an adult”.

2. Ask the user to enter

two numbers. Add the
numbers together, if
the total is over 50
display the output “Too
high”, otherwise
display the total.

3. Ask the user to enter

their favourite colour.
If they enter “red”
display “I like red too”,
if they enter “blue”
display “Why do you
like blue? I prefer red”
and if they enter
anything else display
“That is a strange
colour to like”.

© Nichola Wilkin Ltd 2020 Page 26

www.nicholawilkin.com
Nesting statements
So far we have looked at loops and we have looked at if statements. Now
we are going to have a go at nesting them together. This means that a
statement goes inside another statement. You need to be especially careful
about indenting statements here as it shows that one block of pseudocode is
inside another.
num = input(“Enter a number”)
message = input(“Enter a message”) Here the for loop
if num >= 5 and num <= 10 then
for i = 1 to num Is inside the if
print(message) statement and the
next i indenting shows
else num < 5 then this
print(“too low”)
else
print(“too high”)
endif

In the pseudocode above it is asking the user to enter a number and

a message. If the number is between 5 and 10 then display the
message they entered that number of times (this is the nested for
loop). If the number they entered is under 5 display “too low” and if
the number is over 10 display “too high”.

Task 17: Write some pseudocode for the scenario below

Ask the user to enter a

number. If they enter a
number between 10 and
20 display the message
“thank you” three times.
If the number was under
10 or over 20 keep asking
them to try again until
they enter a number
between 10 and 20.

© Nichola Wilkin Ltd 2020 Page 27

www.nicholawilkin.com
Switch case
Another type of selection is the switch case
pseudocode.
switch entry:
case “A”:
print(“You selected A”)
case “B”:
print(“You selected “B”)
default:
print(“Unrecognised selection”)
endswitch

This pseudocode will ask the user to input something

and will check what they have entered. If they
entered the letter “A” it will display the message “You
selected A”, if they entered “B” it will display “You
selected B” but if the user enters anything else it will
display the message “Unrecognised selection”. It
works in a very similar way to an if statement.
However, it should be noted that Python does not
recognise them but forms of the switch statement do
work in other programming languages.

Often the switch statement performs the same tasks

as an if statement and it is only personal preference
as to which is used. In the example below these two
pieces of code are both performing the same task
based on an integer the user enters called “num”.

If statement Switch statement

if num <=10 then switch entry:

print(“Too low”) case num <= 10:
elseif num >=50 then print(“Too low”)
print(“Too high”) case num >= 50:
else print(“Too high”)
print(“Thank you”) default:
endif print(“Thank you”)
endswitch

© Nichola Wilkin Ltd 2020 Page 28

www.nicholawilkin.com
 Task 18: Write this if statement using a switch case statement

num1 = int(input(“Enter number: ”)

if num1 <= 100 then
num2 = int(input(“Enter another number: ”)
num1 = num1 + num2
else
num1 = num1 + 10
endif
print(num1)

© Nichola Wilkin Ltd 2020 Page 29

www.nicholawilkin.com
Dealing with strings
A string is a sequence of characters.
These can include letters (both upper and A string is a sequence
lower case), numbers (that you do not of characters
want to use as part of a calculation) and
special characters (such as £, a space or even a line break). Strings are
usually identified by using speech marks around them such as “Hello world”.

Below is a table containing some pseudocode specifically used when

dealing with strings.

Example Output Description

Tells you the
name = “Peter Smith” length of a string
print(name.length) 11
(including
spaces)
Shows the
characters within
a string from the
subject = “computing”
print(subject.subString(2,3)) “mpu” start position
(counting from 0)
and showing 3
characters
Using the +
symbol with
“computer”+”science”
strings joins them
“computerscience”
together; this is
known as
concatenation

Task 19: Write the pseudocode which asks the user to input a
number and their first name. Divide the number by 3 and
join this to the last letter of their name.

© Nichola Wilkin Ltd 2020 Page 30

www.nicholawilkin.com
ASCII and Unicode
ASCII and Unicode are two different character encodings. They are the
standards on how to represent different characters in binary so that they can
be written, stored, transmitted and read in digital media. Each character is
given a unique number that it represents.

ASCII contains 128 Unicode contains over

characters 120,000 characters
For instance “a” is 97 and an “A” is 65. All symbols and numbers also have a
number attached so “{“ is 123 and “8” is 56. ASCII is the original code and
defines just 128 characters, but Unicode contains more than 120,000
characters and allows characters and symbols from the different alphabets
from around the world to be used.

Example Output Description

int(“16”)
Converts a string to an integer so it
16
can be used in calculations
Converts a string to a floating point
float(“16.4”)
data type (a number that includes a
16.4
decimal point) so it can be used in
calculations
Converts an integer to a string so it
str(45) “45” can be joined (concatenated) to
other strings

ASC(“a”)
Converts a character to the
97
ASCII/Unicode number

CHR(97)
Converts an ASCII/Unicode number to
“a”
the correct character

© Nichola Wilkin Ltd 2020 Page 31

www.nicholawilkin.com
Arrays
Arrays allow multiple values to be stored
as a single piece of data

Variables allow a single value to be stored under a single

variable name, but arrays allow multiple values to be
stored under a name. In the programming language
called Python these are called lists but are usually referred
to by programmers as arrays.

It may be easier to think of arrays as a “block of data”.

“Red” “Yellow” “Blue” “Green” “Black”

Here we have an array containing lots of colours so let’s call this array
“colours”. Each of the different items in that block has a unique number and
these are numbered from 0.

0 1 2 3 4
colours
“Red” “Yellow” “Blue” “Green” “Black”

In this example colours[2] would mean “Blue” and colours[0] would be

“Red”. The square brackets are used to identify the position in an array.

If we wanted to add another item to the array how do you think we could do
that in pseudocode?
colours[5] = “Pink”

You may want a block of data that contains more than a single row of data:

characters 0 1 2

0 “Stewie” “Peter” “Brian”

1 “Bart” “Lisa” “Homer”

2 “Leonard” “Sheldon” “Penny”

3 “Barney” “Robin” “Ted”

© Nichola Wilkin Ltd 2020 Page 32

www.nicholawilkin.com
This requires two numbers; the first is for the row number and the second for
the column within that row. The pseudocode characters[3,1] would
return “Robin”. How could you change “Brian” in the first row to “Meg”?
characters[0,2] = “Meg”

Task 20: Write some pseudocode to ask the user to enter

three new names to an array called names and these should
be added as an extra row

© Nichola Wilkin Ltd 2020 Page 33

www.nicholawilkin.com
External files
It is possible to link and save data to external records which can be text files
(.txt) or comma separated values files (.csv).

Reading from external files

myFile = openRead(“names.txt”)
while NOT myFile.endOfFile()
print(myFile.readLine())
endwhile
myFile.close()

This will read a text file called “names.txt” and it will read and display each
line separately.

Writing to an external file

newName = input(“Enter name: ”)
myFile = openWrite(“names.txt”)
myFile.writeLine(newname)
myFile.close()

This will ask the user to enter a name, open the “names.txt” file and add the
new name to the end of the text file.

Task 21: Write pseudocode which will use a loop to ask the
user to enter three numbers and save them each in a file. It
should then read the data from the file and display each
individually

© Nichola Wilkin Ltd 2020 Page 34

www.nicholawilkin.com
Sub programs
In programming, you may have heard the terms “functions”, “procedures” or
“sub programs”. What are they and what is the difference? A sub program
(also known as a subroutine) is a set of instructions that are grouped together,
given a name and this sequence would be executed by running (calling)
that name in the main program. Functions and procedures are both classed
as sub programs but are slightly different from one another:

Functions return values Procedures don’t

back to the main return a value back to
program the main program

To define a sub program, it needs to be defined before it is to be called by

the main program. Sub programs usually appear near the top of the
pseudocode. In the example below, we have created a function called
“addnums” which will take the values x and y from the main program, add
them together and return the answer to the main program. Because we are
returning a value back to the main program, this makes it a function and not
a procedure. In this example the function is shown in bold and the main
program is in italics to help you differentiate which is which, but this is not how
it would usually be formatted.
function addnums(x,y)
answer = x + y
return answer
endfunction

x = input(“Enter x: ”)
y = input(“Enter y: ”)
addnumbs(x,y)
print(answer)

Please note: as the sub program uses the

variables x and y from the main algorithm, it
needs to include these in the brackets after
the sub program name to show they are
existing variables being passed into the sub
program and not generating new variables.

© Nichola Wilkin Ltd 2020 Page 35

www.nicholawilkin.com
 Task 22: Write pseudocode which will ask the user to enter
three numbers. It should then use these three values in a sub
program called avnum which will work out the mean
average (add them together and divide it by 3) and return
the average which should be displayed as the output in the
main program

© Nichola Wilkin Ltd 2020 Page 36

www.nicholawilkin.com
 Flowcharts
Flowcharts are a graphical representation of the routes
available through an algorithm

Task 23: What do you think this flowchart is showing? Write

your solution using pseudocode

© Nichola Wilkin Ltd 2020 Page 37

www.nicholawilkin.com
Flowchart symbols
You may have noticed there are 4 different symbols used in the flow chart.

Symbol Meaning

Terminators used to define where the algorithm starts

and stops

Input / Output used to define the user input or the

output to be shown

Process used to define something that has to be

performed by the algorithm for instance a
mathematical function etc.

Decision / Selection used to define a question and

multiple arrows will define the possible outcomes

Sub program used to show where the main program

will be diverted to a sub program (shown as a
separate flow chart). See page 45 for more
information

When drawing a flow chart there are several rules you should be aware of:

• Start from the top of the flowchart and work down.

• Each flowchart must have only one start terminator.
• Use vertical and horizontal lines only, never use diagonal lines or
curved lines but you can use lines containing elbows (as shown on the
right) if necessary.
• Use arrows at the end of the lines to signify the direction of movement
through the flowchart.
• When lines join, the flow of control merges and follows the same direction.
• Ideally, lines should not cross each other. However, when this is not
possible use a bridge (shown on the right) to show the lines are
crossing and not merging.
• The lines must not split. Use decision diamonds to give the flow of control a
choice of paths to follow, but it can only follow one of these paths at a time.

© Nichola Wilkin Ltd 2020 Page 38

www.nicholawilkin.com
 Task 24: Using the symbols and rules draw a flowchart for the
following pseudocode. If you are filling this in electronically,
please create your flow diagram in another package such
as PowerPoint and then save it as an image (either .jpg or
.png). To insert your image into the space below, click on
the area and then select your image file.

price = input(“Enter the price: ”)

if price > 30 then
discount = price * 25%
else
discount = price * 15%
endif
newprice = price – discount
print(newprice)

© Nichola Wilkin Ltd 2020 Page 39

www.nicholawilkin.com
Drawing loops in flowcharts
When we looked at the different types of loop in pseudocode
we learnt that:

• For - will repeat an action a set number of times and is also known as a
counting loop
• Repeat…until – Keeps repeating the actions UNTIL it meets a condition
• While – keeps repeating an action AS LONG AS a condition is being met

In a while loop the condition is being tested at the beginning of the loop:
a = 0
while a != 4
a = input(“Enter a number”)
ENDWHILE

This is the same when we draw a while loop flowchart:

In a repeat until loop the condition is tested AT THE

END of the loop, rather than at the beginning:

total = 0
repeat
a = input(“Enter a number”)
total = total + a
UNTIL total = 10

© Nichola Wilkin Ltd 2020 Page 40

www.nicholawilkin.com
In a for loop you need to include additional processes such as setting a
starting value before the loop and a process to change the count value.

for a = 1 to 10
print(a)
Next a

© Nichola Wilkin Ltd 2020 Page 41

www.nicholawilkin.com
 Task 25: Draw a flowchart for the following pseudocode. If
you are filling this in electronically, please create your flow
diagram in another package such as PowerPoint and then
save it as an image (either .jpg or .png). To insert your image
into the space below, click on the area and then select your
image file.

num = input(“Enter a number”)

if num <= 10 then
for a = 1 to num
print(a)
next a
else
print(“Too high”)
endif

© Nichola Wilkin Ltd 2020 Page 42

www.nicholawilkin.com
Understanding flowcharts
Look at the following flowchart:

Task 26: Identify the following boxes that appear in the

flowchart above by drawing ALL the boxes that match the
labels.

Inputs

Processes

Outputs

© Nichola Wilkin Ltd 2020 Page 43

www.nicholawilkin.com
 Task 27: Use the space below to describe, in your own
words, what the flowchart is showing. Clearly identify the
inputs, processes and outputs in your description.

© Nichola Wilkin Ltd 2020 Page 44

www.nicholawilkin.com
Showing sub programs in flowcharts
To refer to a sub program in a flowchart you use the following symbol:

This example refers to a sub program called avnum which is using the
variables num1, num2 and num3, which we have already defined in the main
part of the algorithm. This is what it would look like in a flow chart.

The larger flowchart on the left is the main flowchart, identified by the start
terminator at the top. The smaller flowchart on the right is the sub program
and instead of using the start terminator it refers to the name of the sub
program, in this case avnum. As you can see this sub program is a function as
it returns the value average back to the main program.

© Nichola Wilkin Ltd 2020 Page 45

www.nicholawilkin.com
 Task 28: Draw a flowchart for the following pseudocode. If
you are filling this in electronically, please create your flow
diagram in another package such as PowerPoint and then
save it as an image (either .jpg or .png). To insert your image
into the space below, click on the area and then select your
image file.

function firstname()
firstname = input(“Enter first name: ”)
name = firstname
return name
endfunction

function wholename()
firstname = input(“Enter first name: ”)
surname = input(“Enter surname: ”)
name = firstname + surname
return name
endfunction

num = int(input(“Enter number: ”))

if num < 10 THEN
firstname()
else
wholename()
endif
print(“Hello” + name)

What would the output be where the user enters the number 6 and their
name is Simon Jenkins?

© Nichola Wilkin Ltd 2020 Page 46

www.nicholawilkin.com
 High-level programming
languages
Programming languages such as Python, Java, SQL and C++ are all classed
as high-level languages as they have been developed to be a little like
a human language. They use English words to make the programming a lot
easier and a single command can perform what would take up several lines
of machine code.

Task 29: Write the program for the following flow diagram
using a high-level programming language, such as Python.

© Nichola Wilkin Ltd 2020 Page 47

www.nicholawilkin.com
Refining programs
Even though a program may be working correctly, it may not be the most
efficient solution and there may be a better way of creating the program.
This is known as refining the program.

Task 30: Have a look at the following program that was

created in Python. There is a better, more efficient way of
writing the program. Write a program that does the same
thing but using less code in the space below.

© Nichola Wilkin Ltd 2020 Page 48

www.nicholawilkin.com
 Identify common errors
What are the different types of error?
There are three main types of error that can occur when programming:

• Syntax
• Runtime
• Logic

Syntax error
This is easy to notice, and Python will usually spot these as you type in the
code and not allow the program to run unless it is fixed. A syntax error is one
that breaks the rules for how the code is supposed to be entered. Python is
very strict about some things such as indenting correctly, including a “:” at
the end of the first line of if statements or loops etc.

If you have a syntax error Python will normally start behaving in an odd way.
For instance, if you miss off a speech mark at the end of a statement the rest
of the text will still be appearing in green which is the first indication that it is
not happy with something you have done. Alternatively, if you miss off a
close bracket then the cursor will appear indented at an odd position on the
next line.

Task 31: Have a look at the following lines of code for Python.
Try and spot the syntax error and write the correct code next
to it.
Code that contains the error Corrected Code
name=input(“Enter your name:)

num=int)input(“Enter a number: ”)

if num > 100

Run-time error
These only appear once you are attempting to run the program and they will
cause the program to crash (stop working) and display an error message.

The error messages look scary but try to look for clues int eh error message
that will tell you the following:

• Where is the error occurring?

• Which line of code does it have a problem with?
• What is it trying to tell you about that code?

Have a look at a simple program and the error message that occurs when
the program is run.

© Nichola Wilkin Ltd 2020 Page 49

www.nicholawilkin.com
When the user tries to run the program, they get this error message.

What is going wrong?

It does not like the line “answer = num / 2” and is saying

you cannot use a division “/” on a “str” and an “int”. It
thinks the “num” part is still a string as it was not cast as an integer in the first
line.

The correct code should be:

Task 32: Work out what has gone wrong in this program

When the user runs it they get this error message:

Now answer these questions:

Where is the error occurring?

Which line of code does it

have a problem with?

What is it trying to tell you

about that code?

© Nichola Wilkin Ltd 2020 Page 50

www.nicholawilkin.com
Logic errors
These are the hardest to identify as it looks like your program works but it is
outputting the wrong answer. It is only when you test the program you realise
it is not working as it should, but you will not get an error message.

Consider this program:

When the user enters a 5 they want the message “Thank you” displayed but it
is showing “Too high”. Likewise, when they enter a 15 they want the message
“Too high” displayed but it is displaying “Thank you”. What has gone wrong?

If we look at the if condition “if num <= 10:” it is using the wrong symbol it
should use “>=”.

It is important to test the programs thoroughly using test data:

• Test all possible inputs for an if statement (test it at least twice)

• Test using extreme data (data that is on the edge of what is acceptable, in
this case 10)

© Nichola Wilkin Ltd 2020 Page 51

www.nicholawilkin.com
 Trace Tables
Trace tables are used to help the programmer either plan their programs or
check to see what is happening in the program after it has been created. It
sets out the variable names and allows the developer to see what will
happen to each variable as the program runs.

How do you create a trace table?

Create a table that has enough columns for each variable and an additional
one entitled output. If we have a look at this flow diagram.

And here is our Python program that accompanies it:

Creating the trace table

So, lets create our trace table. This program has three variables called num1,
total and num2 and we need to add an output column:

num1 total num2 Output

© Nichola Wilkin Ltd 2020 Page 52

www.nicholawilkin.com
Filling in the trace table
We will start at the top. We are asking the user to enter value and they could
enter anything so let us assume they enter a 2 to start with:

num1 total num2 Output

2 2

Create a new row when…

• You reach a decision diamond or

• You need to write a new value to a variable and it has already been filled in
for that row

Now we hit the diamond and as the total is under 10 we follow the “yes”
route through the flow diagram and we need to start a new row. We ask the
user to enter another number, let’s assume they enter a 5 this time, and this
gets added to the total.

num1 total num2 Output

2 2

7 5

Again, we find ourselves back at the diamond and it is still under 10. We
follow the “yes” route and it will ask us to enter another number so let’s enter
a 4.

num1 total num2 Output

2 2

7 5

11 4

© Nichola Wilkin Ltd 2020 Page 53

www.nicholawilkin.com
And we are back once again to the diamond but this time the value of total
is now over 10 so we follow the “no” route through the flow diagram and
display the output.

num1 total num2 Output

2 2

7 5

11 4

11

Here is our final trace table and if we run the program and enter the values 2,
5 and 4 this is the output:

Let’s have a look at another program, this time using a for loop. Here is our
for loop flow diagram:

Here is the Python program that would accompany that flow diagram:

We have one variable called “count” that is starting at 0.

© Nichola Wilkin Ltd 2020 Page 54
www.nicholawilkin.com
As we only have one variable, our trace table will look as follows. Remember
you need a column for each variable and one for the output:

count Output

Start with the starting value of the variable. In this case count is assigned the
value 0.

count Output

Whenever you reach a decision diamond start a new row in your trace table,
even if it means leaving blank cells in that row.

After count is set to 0 it gets to a diamond, so we start a new row:

count Output

Now fill in the next row following the correct route of the flow diagram, in this
case the “no” route. The output will be whatever the count value is set to (in
this case 0) and then 1 is added to the count. Don’t forget our output is
displayed BEFORE the variable changes its value, so try not to read the trace
table from left to right but instead look at the columns in the order they will be
displayed or altered. In this example our output occurred before the count
value was added so the output column is read first.

count Output

1 0

© Nichola Wilkin Ltd 2020 Page 55

www.nicholawilkin.com
We follow our flow diagram back to the diamond so start a new line and
repeat the process.

count Output

1 0

2 1

Again, we are back at the diamond so start a new line and repeat the
process.

count Output

1 0

2 1

3 2

This time when we get back to the diamond, we need to start a new row but
as the variable is now at 3 we follow another route, the “yes” part of the flow
diagram, and this changes from only displaying the count value to
displaying the message “You have reached 3”.

count Output

1 0

2 1

3 2

You have reached

3

© Nichola Wilkin Ltd 2020 Page 56

www.nicholawilkin.com
And sure enough, when we run the program this is the output:

Task 33: Complete the trace table for the following

pseudocode if the user enters 2 to start with and then when
they are asked to enter another number, they enter a 5. You
do not need to fill in all of the rows.
function lownum(num)
num = num * 2
return num
endfunction

function highnum(num)
num2 = input(“Enter another number: ”)
num = num + num2
return num
endfunction

num = int(input(“Enter number: ”))

while num < 10 THEN
num = lownum(num)
endwhile
num = highnum(num)
print(num)

num num2 output

© Nichola Wilkin Ltd 2020 Page 57

www.nicholawilkin.com
 Standard searching algorithms
We are going to look at two search algorithms:

• Linear search
• Binary search
At the back of this workbook book you will see a number of squares
containing numbers. Print out this page and carefully cut out the numbers
along the dotted lines and pick out those cards which have the numbers 1 to
10 on them and put the rest in a neat pile to one side (we will be using these
later).

Shuffle the remaining cards (numbered 1 to 10) and put them face down on
the desk in front of you in one long line.

Linear search
We are going to perform a linear search algorithm.

Algorithm Flowchart

1. Write position = 0 in the first row on

the next page.

2. Turn over the card in that position

and write down the number next
to the position.

3. Is the card the value you are

looking for?

4. If yes then stop. If no then add

one to the position and repeat
steps 2, 3 and 4.

Watch this video: https://youtu.be/XJuM1v48V78

© Nichola Wilkin Ltd 2020 Page 58

www.nicholawilkin.com
 Task 34: Using the algorithm on the previous page write
down the position and the value of the card at that position.
Stop when you have found the card with the value you are
searching for. You are going to try this exercise twice,
remember to shuffle the cards before you start the second
exercise
What are you searching
Position Card Value
for?

Search for the value 4

What are you searching

Position Card Value
for?

Shuffle the cards and

lay them in a line on
the surface in front of
you before attempting
this search. Search for
the value 8

© Nichola Wilkin Ltd 2020 Page 59

www.nicholawilkin.com
Binary search
A binary search only works if the list is
sorted so lay out your cards in order from 1 A binary search only
to 10 and turn them over so they are all works if the list is sorted
face down. Binary numbers contain 2
digits (a 1 and 0). A binary search works
by splitting the list into two.

1. Find the middle card (if there is no middle card move to

the next card to the left).

2. Turn it over. If that is the card you are looking for, stop.

3. If the value you are searching for is higher than the card
Algorithm you have turned over discard all the cards to the left of
the turned over card. If the value is lower than the card
discard all the cards to the right.

4. Discard the turned over card.

5. Repeat steps 2, 3 and 4.

Flowchart

Watch this video: https://youtu.be/TY-sTiEeU1w

© Nichola Wilkin Ltd 2020 Page 60

www.nicholawilkin.com
 Task 35: Using the algorithm on the previous page write
down the position and the value of the card at that position.
Make sure your cards are sorted into order and placed face
down on the table in front of you before you start each
round
What are you searching
Position Card Value
for?

Search for the value 6

What are you searching

Position Card Value
for?

Sort the cards and lay

them in a line on the
desk in front of you
before attempting this
search. Search for the
value 3

© Nichola Wilkin Ltd 2020 Page 61

www.nicholawilkin.com
 Task 36: You are going to be comparing the two algorithms
by performing the same searches and record the number of
times the algorithm needs to be repeated in order to find the
correct value
Linear Search Binary Search
Remember the cards should be in a Remember the cards must be in the
random order before you start each sorted order before you start each
search. search.

1 round = Starting from the left, turn 1 round = Turn over the middle card
over one card. and discard the cards you do not
need.

Value you are Number of Value you are Number of

looking for rounds it took looking for rounds it took

11 11

16 16

6 6

13 13

1 1

9 9

5 5

20 20

© Nichola Wilkin Ltd 2020 Page 62

www.nicholawilkin.com
 Task 37: Ask yourself the following questions

1. Which of the two search algorithms that we have looked at in this

chapter required the data to be in a sorted order?

2. Explain how a linear search works.

3. What are the advantages and disadvantages of the linear search?

4. Explain how a binary search works.

5. What are the advantages and disadvantages of the binary search?

6. Which do you think is likely to be more efficient when dealing with a

long list of data?

© Nichola Wilkin Ltd 2020 Page 63

www.nicholawilkin.com
 Standard sorting algorithms
We are going to look at three sorting algorithms

• Bubble sort
• Merge sort
• Insertion Sort

Bubble sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the
adjacent elements if they are in wrong order.

Description Example
Step 1: Starting
positions of all the
numbers
Step 2: Look at the
first two numbers

Step 3: If num1 is
greater than num2
swap them over

Step 4: Move onto

the next pair of
numbers and repeat
step 3
Step 5: Keep
repeating steps 3
and 4 until you get to
the end of the array

© Nichola Wilkin Ltd 2020 Page 64

www.nicholawilkin.com
 Description Example
Step 6: When you get
to the end of the
array, if there have
been changes
repeat steps 3 to 5.
Keep repeating until
you get to the end of
the array with no
changes

Step 7: If you get to

the end of the array
with no changes stop
the algorithm

© Nichola Wilkin Ltd 2020 Page 65

www.nicholawilkin.com
Follow these steps to sort them using the merge sort.

1) Set positionA to 0 and positionB to 1

2) Set a variable called changes to “No”
3) If postionB is lower than positionA swap them over and alter the changes
variable to “Yes”
4) Add 1 to postionA and postionB
5) Repeat steps 3 and 4 until you reach the end of the array
6) If the changes array = “Yes” then reset postionA to 0 and postionB to 1 and
change the variable changes to “No”
7) Repeat steps 3 to 6 until you reach the end of the array and the changes
variable is still “No”

Here is the flowchart for the algorithm:

Watch this video: https://youtu.be/V-XP4gqxFZI

© Nichola Wilkin Ltd 2020 Page 66

www.nicholawilkin.com
If you have not already cut them out, cut out the numbers from the back of
this workbook. Pick out those cards which have the numbers 1 to 10. Shuffle
the cards and put them face up on the desk in front of you in one long line.

Practise performing the bubble sort with your cards until you feel you
understand how it works.

Task 38: Without looking back at the previous pages,

describe in your own words how a bubble sort works

© Nichola Wilkin Ltd 2020 Page 67

www.nicholawilkin.com
Merge sort
There are two stages to performing a merge sort; the first divides the cards
into separate components.

The second stage repeatedly merges them to produce new sorted sub-arrays
until there is only one large sorted array remaining.

Stage 1: Take an array and keep dividing in half until you have separate sub-
arrays

Stage 2: Sort the sub-arrays and merge them back together until you have a
complete list once more

Lets have a look at how the algorithm works with just 4 numbers.

Description Example
Step 1: Starting positions of all
the numbers

Step 2: Split into two groups

Step 3: Repeat Step 2 until they

are all in individual arrays

Step 4: Take the first position of

each array and compare to
the first position of the next
array
Step 5: If the first array value is
higher than the second value
swap places
Step 6: Find the next two arrays

Step 7: Repeat steps 5 and 6

until all the sub-arrays are
sorted. In this example we only
have two sub-arrays so once
both of these are sorted we
can move onto the next step
Step 8: Once all the sub-arrays
are sorted you can now check
the first position of the first array

© Nichola Wilkin Ltd 2020 Page 68

www.nicholawilkin.com
 Description Example
and the first position of the
second array
Step 9: Whichever value is
lower move to another array

Step 10: Now repeat steps 8

and 9. Here we are checking if
the first position of the first array
is lower than the first position of
the second array

Step 11: Here you can see the

lower figure has been moved
to the new array we are
creating

Step 12: Here we are checking

the first value of each array
(there is only one value left in
each array which makes this
easier)

Step 13: Here the lower value

has been moved which only
leaves one value left

Step 14: Once the final number

has been added to the new
array you can see the
complete list of numbers has
been sorted

© Nichola Wilkin Ltd 2020 Page 69

www.nicholawilkin.com
Some people find it easier to picture a merge sort as follows:

Follow these steps to sort them using the merge sort.

1) Split the array in half

2) Repeat step 1 until there is only 1 value in each of the sub-arrays
3) Take the first value of the sub-array and compare it with the first value of the
next sub-array. If the first number is smaller than the second number then store
the first number in a larger array, otherwise store the second number in the
larger array
4) Look at the next two sub-arrays and repeat step 3 until all the sub-arrays have
been sorted into their own larger arrays
5) Repeat step 4 until all the larger arrays have been sorted into one single array
and your numbers should be sorted into order

© Nichola Wilkin Ltd 2020 Page 70

www.nicholawilkin.com
Here it is shown as a flow chart:

Watch this video: https://youtu.be/-v_tAQFUTPw

© Nichola Wilkin Ltd 2020 Page 71

www.nicholawilkin.com
If you have not already cut them out, print cut out the numbers from the
back of this workbook. Pick out those cards which have the numbers 1 to 8.
Shuffle the cards and put them face up on the desk in front of you in one
long line.

Practise performing the merge sort with your cards until you feel you
understand how it works. Try performing the merge sort using an odd number
of cards to see how it would work.

Task 39: Without looking back at the previous pages,

describe in your own words how a merge sort works

© Nichola Wilkin Ltd 2020 Page 72

www.nicholawilkin.com
Insertion sort
Insertion sort works by removing the first item in the array and moving into
another array sorting it into position immediately before bringing in the next
item.

Description Example
Step 1: Split the
list into sorted
and unsorted
arrays. Here
the unsorted
array is after
the dotted line
and the sorted
array, which is
presently
empty, is
before the
dotted line
Step 2: Move
the first item
from the array
list to the sorted
array. In this
example 2 is
the only item in
the sorted array
so it must be in
the right order
Step 3: Collect
the next item
from the
unsorted array
and move it to
the end of the
sorted array.
Check that
new item. Is it
smaller than the
previous item?
If it is then swap
them over. In
this case it is
larger, so we
leave it in that
position and
move onto the
next step

© Nichola Wilkin Ltd 2020 Page 73

www.nicholawilkin.com
 Description Example
Step 4: Collect
the next item
from the
unsorted array
and move it to
the end of the
sorted array
Step 5:
compare the
new item with
the previous
number in the
array. If it is less
than the
previous value
move it in front
of that item in
the array. In
this case we
are comparing
1 (the new
item) with 4
(which is
already in the
sorted array).
As 1 is less than
4 we move it
forward a
position in the
list
Step 6: We
compare the
new item with
the item
already in the
array. As 1 is
less than 2 we
swap their
positions

© Nichola Wilkin Ltd 2020 Page 74

www.nicholawilkin.com
 Description Example
Step 7: As the
new item is now
at the front of
the sorted array
we can no
longer keep
comparing it so
we start the
loop again as
we still have
items in the
unsorted array
Step 8: Collect
the next item
from the
unsorted array

Step 9: Place
the new item at
the end of the
sorted array
and compare it
to the previous
item. In this
case 5 is not
less than 4 so
we do not
need to swap
anything
around and
can repeat the
loop as we still
have items in
the unsorted
array
Step 10: Collect
the next item
from the
unsorted array

© Nichola Wilkin Ltd 2020 Page 75

www.nicholawilkin.com
 Description Example
Step 11: Move it
to the end of
the sorted array
and compare it
with the
previous value.
In this case 3 is
less than 5 so
we swap them
around
Step 12: We
compare it with
the next value.
In this case 3 is
less than 4 so
we swap them
around
Step 13: As 3 is
not less than 2
we do not
need to swap
them and as
there are no
more items in
the unsorted
array we stop
the sort,
knowing that
our list is now
sorted

Follow these steps to sort them using the insertion sort.

1) Split the array into sorted and unsorted arrays

2) Move the first item from the unsorted array to the end of the unsorted array
3) Compare the new item with the previous item in the array. If it is less than the
previous item swap them around and repeat until it no longer needs to be
swapped
4) Repeat steps 2 and 3 until there are no more items in the unsorted array

Here is the flowchart for the algorithm:

© Nichola Wilkin Ltd 2020 Page 76

www.nicholawilkin.com
 Watch this video: https://youtu.be/zi9Ep0Cd7VI

Task 40: Use the cards at the back of this workbook to

practise performing an insertion sort and then write, in your
own words, how the insertion sort works

© Nichola Wilkin Ltd 2020 Page 77

www.nicholawilkin.com
 Number Cards

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

17 18 19 20

© Nichola Wilkin Ltd 2020 Page 78

www.nicholawilkin.com