Robinson Tuition
AS Decision Mathematics 1 · Edexcel 8FM0 · free Further Maths worksheet

Algorithms and sorting

Trace tables for a flow chart or written algorithm, bubble sort and quick sort with each pass shown, the order of an algorithm and estimating run times, the Euclidean algorithm.

12 original questions, 66 marks. Type your answers below for an instant mark and a score (algebra in any equivalent form, e.g. 2sqrt(3) or 2√3), or print the worksheet, mark it with the answers sheet, and use the solutions to see every step written out by hand.

Worksheet PDFWorked solutions PDFAnswers PDF

The questions

1

Use a bubble sort, starting at the left-hand end of the list, to sort these numbers into ascending order.

34 18 52 27 41 9 30

You should show the state of the list after each pass.

4 marks
Show answer
Passes: 18 34 27 41 9 30 52; 18 27 34 9 30 41 52; 18 27 9 30 34 41 52; 18 9 27 30 34 41 52; 9 18 27 30 34 41 52; 9 18 27 30 34 41 52. Sorted: 9 18 27 30 34 41 52
2

A bubble sort is an algorithm of quadratic order. A laptop takes 0.8 seconds to bubble sort a list of 400 names.

  1. Estimate the time it would take to bubble sort a list of 2000 names.

A different algorithm has cubic order. It takes 1.2 seconds when the input has size 50.

  1. Estimate the time it would take when the input has size 200.
4 marks
Show answer
a) 20 seconds b) 76.8 seconds
3

Use the Euclidean algorithm to find the highest common factor of 4199 and 1547. Show each step of your working.

3 marks
Show answer
221
4

Use a quick sort to sort the list below into ascending order. You should show the result of each pass and identify your pivots clearly.

47 12 85 33 60 21 74 9 56 38

4 marks
Show answer
Pivots by pass: 21; 9, 60; 56, 74; 33; 38. Sorted: 9 12 21 33 38 47 56 60 74 85
5

The names of nine members of a chess club are listed below.

Priya   Callum   Zara   Mohammed   Erin   Tomasz   Hannah   Kofi   Beth

Use a quick sort to put the names into alphabetical order. You should show the result of each pass and identify your pivots clearly.

4 marks
Show answer
Pivots by pass: Erin; Beth, Tomasz; Hannah; Mohammed. Sorted: Beth, Callum, Erin, Hannah, Kofi, Mohammed, Priya, Tomasz, Zara
6

The flow chart describes an algorithm.

  1. Trace the algorithm with input N = 40, recording the values of N, a and b each time round the loop. State the output.
  2. Write down the output when the input is N = 90
  3. State what the algorithm finds.
StartInput NLet a = 0 and b = 1Is N ≥ b ?Let N = N - bLet b = b + 2Let a = a + 1Output aStopYesNo
6 marks
Show answer
a) 6 b) 9 c) the integer part of √N
7

The list below is to be sorted into descending order using a bubble sort, starting at the left-hand end of the list.

15 42 8 27 33 19

  1. Carry out the bubble sort, showing the list after each pass.
  2. Find the total number of comparisons and the total number of swaps made.
  3. Find, in terms of n, the maximum number of comparisons needed to bubble sort a list of n numbers.
7 marks
Show answer
a) 42 33 27 19 15 8 b) 14 comparisons, 8 swaps c) n(n - 1)2
8

On average a quick sort has order n log n. A computer takes 0.36 seconds to quick sort a list of 1000 numbers.

  1. Estimate how long it would take to quick sort a list of 8000 numbers.

An algorithm of cubic order takes 0.05 seconds for an input of size 20.

  1. Find the largest input size that the computer can process with this algorithm in one minute.
5 marks
Show answer
a) 3.75 seconds b) 212
9

An algorithm is shown below. INT(x) means the integer part of x.

Step 1  Input a positive integer N
Step 2  Let P = 1 and B = 0
Step 3  Let R be the remainder when N is divided by 2
Step 4  Let B = B + R × P
Step 5  Let N = INT(N ÷ 2)
Step 6  Let P = 10P
Step 7  If N > 0 go to Step 3
Step 8  Output B
Step 9  Stop

  1. Trace the algorithm for N = 45, showing the values of R, B, N and P each time Step 6 is completed. State the output.
  2. Explain what the algorithm does.
  3. Find how many times Step 3 is carried out when N = 1000
6 marks
Show answer
a) 101101 b) writes N in binary c) 10
10

The six distinct integers 24, x, 17, 31, 12, 28 are to be sorted into ascending order using a bubble sort, starting at the left-hand end of the list.

After the first pass the list is   24  17  x  12  28  31

  1. Explain why 24 < x < 31

After the second pass the list is   17  24  12  28  x  31

  1. Find the possible values of x.
  2. Taking the smaller value of x, complete the sort, showing the list after each further pass.
6 marks
Show answer
a) x > 24 (24 and x not swapped) and x < 31 (x did not pass 31) b) 29 or 30 c) 17 12 24 28 29 31; 12 17 24 28 29 31; 12 17 24 28 29 31
11

The list below is to be sorted into descending order.

63 18 45 92 27 71 54 36

  1. Use a quick sort to sort the list. You should show the result of each pass and identify your pivots clearly.
  2. Find the total number of comparisons made in your quick sort.
  3. A bubble sort, starting at the left-hand end, is used on the original list instead. Find the number of passes and the total number of comparisons it makes, and state which method was quicker for this list.
8 marks
Show answer
a) 92 71 63 54 45 36 27 18 b) 16 c) 5 passes, 25 comparisons; quick sort quicker
12

An algorithm is shown below.

Step 1  Input a positive integer n
Step 2  Let i = 1 and T = 0
Step 3  Let j = i
Step 4  Let T = T + j
Step 5  Let j = j + 1
Step 6  If j ≤ n go to Step 4
Step 7  Let i = i + 1
Step 8  If i ≤ n go to Step 3
Step 9  Output T
Step 10  Stop

  1. Trace the algorithm with n = 3, showing the values of i, j and T each time Step 4 is completed. State the output.
  2. Explain why the output is 12 + 22 + ... + n2 and hence write down the output in terms of n.
  3. Show that Step 4 is carried out 12n(n + 1) times and state the order of the algorithm.
  4. The algorithm takes 0.004 seconds when n = 500. Estimate the time it takes when n = 3000
9 marks
Show answer
a) 14 b) 16n(n + 1)(2n + 1) c) quadratic, order n2 d) 0.144 s

Your score

Answer the questions above and your score appears here.

Every question here is original and written by Robinson Tuition. It follows the Edexcel AS Further Mathematics specification and suits AQA and OCR Further Maths too; this is not an exam-board paper.

All AS Decision Mathematics 1 topics