Examples

Trace Tables

Write down inputs, outputs and variables needed in a readable format. e.g.

  • Below is a flowchart to determine the highest number of ten user-entered numbers

  • The algorithm prompts the user to enter the first number which automatically becomes the highest number entered

  • The user is then prompted to enter nine more numbers.

    • If a new number is higher than an older number then it is replaced

  • Once all ten numbers are entered, the algorithm outputs which number was the highest

  • Example test data to be used is: 4, 3, 7, 1, 8, 3, 6, 9, 12, 10

flowchart question

answer:

Count

Highest

Number

Output

1

 

 

Enter ten numbers

 

4

 

Enter your first number

2

 

3

Enter your next number

3

7

7

 

4

 

1

 

5

8

8

 

6

 

3

 

7

 

6

 

8

9

9

 

9

12

12

 

10

 

10

12 is your highest number

  • Only write when change is made in the program, convert python into flowchart if necessary

SORTING ALGORITHMS

Bubble

Bubble Sort

Step

Instructions

1

Compare the first two values in the dataset

2

IF they are in the wrong order...

  • Swap them

3

Compare the next two values

4

REPEAT step 2 & 3 until you reach the end of the dataset (pass 1)

5

IF you have made any swaps...

  • REPEAT from the start (pass 2,3,4...)

6

ELSE you have not made any swaps...

  • STOP! the list is in the correct order

Insertion

Step

Instruction

1

Take the first value in the dataset, this is now the sorted list

2

Look at the next value in the dataset and compare it to the first value

IF it is smaller

  • insert it into the correct position to the left

3

ELSE

  • Keep in the same position

4

REPEAT steps 2 & 3 until all values in the dataset have been compared, the list should now be in order

Insertion Sort Algorithm

Merge

Step

Instruction

1

Divide the dataset into individual datasets by repeatedly splitting the dataset in half (DIVIDE)

2

Merge pairs of sub-datasets together by comparing the first value in each dataset (CONQUER)

3

REPEAT step 2 until all sub-datasets are merged together into one dataset

Merge Sort

SEARCHING ALGORITHMS

Linear Search

1

Check the first value

2

IF it is the value you are looking for

  • STOP!

3

ELSE move to the next value and check

4

REPEAT UNTIL you have checked all values and not found the value you are looking for

Linear Search

Binary Search

1

Identify the middle value (12) (total values + 1 divided by 2, if 0.5 then round up)

 

2

5

7

12

15

22

46

2

Compare to the value you are looking for - Is 12 == 7?

3

IF it is the value you are looking for...

  • Stop! - 12 is not equal to 7

4

ELSE IF is it bigger than the one you are looking for... Is 12 > 7? YES

  • Create a new list with the values on the left of the middle value

2

5

7

5

IF it is smaller than the one you are looking for...

  • Create a new list with the values on the right of the middle value

6

REPEAT with the new list

2

5

7


Is 5 == 7? NO

Is 5  > 7? NO - create new list with values to the right

7


Is 7 == 7? YES

STOP!

Binary Search