| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2019 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Shuttle Sort Execution |
| Difficulty | Moderate -0.5 This is a straightforward algorithm trace question requiring careful step-by-step execution of a given sorting algorithm (shuttle sort). Part (a) requires simple recall, part (b) is mechanical tracing, and parts (c)-(d) involve counting operations and applying quadratic complexity—all standard exam techniques with no novel problem-solving required. Slightly easier than average due to the algorithmic/procedural nature rather than mathematical insight. |
| Spec | 7.03a Algorithm definition: input, output, deterministic, finite7.03c Working with algorithms: trace, interpret, adapt7.03j Sorting: bubble sort and shuttle sort |
| Answer | Marks | Guidance |
|---|---|---|
| Shuttle (sort) | B1 [1.2] | Or insertion |
| Answer | Marks | Guidance |
|---|---|---|
| First row correct in all four columns | B1 [1.1] | |
| \(L = 6, N = 9\) and then \(N = 5\) | B1 [1.1] | |
| \(L = 5, 6, 9\) (in this order) with \(N = 7\) | B1 [1.1] | Treat any blank cells with values on that column in a row above and a row below as rolling down from the row above |
| \(L = 5, 6\) (in this order) with \(N = 6\) | B1 [1.1] | |
| \(\{\text{input list}\} \cup \{N\} \cup \{\text{output list}\} = \{4, 5, 6, 6, 7, 9\}\) in at least 4 different rows | B1 [1.1] |
| Answer | Marks | Guidance |
|---|---|---|
| 8 | B1ft [1.1] | Number of different rows, excluding 'print' row |
| Answer | Marks | Guidance |
|---|---|---|
| 15 | B1 [2.2b] | \(1+2+3+4+5\) |
| Answer | Marks | Guidance |
|---|---|---|
| Sorting is \(O(n^2)\) or quadratic order | M1 [1.1] | Allow M1 for \(\frac{1}{2}n(n-1)\) or any quadratic function, algebraic |
| \(15 \times \left(\frac{300}{60}\right)^2\) | M1 [1.1] | Size of problem is \(\times\frac{300}{60} = \times 5\); Or \(k \times 60^2 = 15\) so \(k = \frac{1}{240}\); M0, M1 for treating problem as \(O(n)\) or \(O(n^3)\) |
| \(= 375\) seconds | A1 [2.2b] | cao, with units; Or 6 minutes 15 seconds |
# Question 3:
## Part (a)
Shuttle (sort) | **B1** [1.2] | Or insertion
## Part (b)
First row correct in all four columns | **B1** [1.1] |
$L = 6, N = 9$ and then $N = 5$ | **B1** [1.1] |
$L = 5, 6, 9$ (in this order) with $N = 7$ | **B1** [1.1] | Treat any blank cells with values on that column in a row above and a row below as rolling down from the row above
$L = 5, 6$ (in this order) with $N = 6$ | **B1** [1.1] |
$\{\text{input list}\} \cup \{N\} \cup \{\text{output list}\} = \{4, 5, 6, 6, 7, 9\}$ in at least 4 different rows | **B1** [1.1] |
## Part (c)(i)
8 | **B1ft** [1.1] | Number of different rows, excluding 'print' row
## Part (c)(ii)
15 | **B1** [2.2b] | $1+2+3+4+5$
## Part (d)
Sorting is $O(n^2)$ or quadratic order | **M1** [1.1] | Allow M1 for $\frac{1}{2}n(n-1)$ or any quadratic function, algebraic
$15 \times \left(\frac{300}{60}\right)^2$ | **M1** [1.1] | Size of problem is $\times\frac{300}{60} = \times 5$; Or $k \times 60^2 = 15$ so $k = \frac{1}{240}$; M0, M1 for treating problem as $O(n)$ or $O(n^3)$
$= 375$ seconds | **A1** [2.2b] | cao, with units; Or 6 minutes 15 seconds
---3
\begin{enumerate}[label=(\alph*)]
\item Give an example of a standard sorting algorithm that can be used when some of the values are not known until after the sorting has been started.
Becky needs to sort a list of numbers into increasing order.\\
She uses the following algorithm:\\
STEP 1: Let $L$ be the first value in the input list.\\
Write this as the first value in the output list and delete it from the input list.\\
STEP 2: If the input list is empty go to STEP 7.\\
Otherwise let $N$ be the new first value in the input list and delete this value from the input list.
STEP 3: $\quad$ Compare $N$ with $L$.\\
STEP 4: If $N$ is less than or equal to $L$
\begin{itemize}
\item write the value of $N$ immediately before $L$ in the output list,
\item replace $L$ with the first value in the new output list,
\item then go to STEP 2.
\end{itemize}
STEP 5: If $N$ is greater than $L$
\begin{itemize}
\item if $L$ is the value of the last number in the output list, go to STEP 6;
\item otherwise, replace $L$ with the next value in the output list and then go to STEP 3.
\end{itemize}
STEP 6: $\quad$ Write the value of $N$ immediately after $L$ in the output list. Let $L$ be the first value in the new output list and then go to STEP 2.
STEP 7: Print the output list and STOP.
\item Trace through Becky's algorithm when the input list is
$$\begin{array} { l l l l l l }
6 & 9 & 5 & 7 & 6 & 4
\end{array}$$
Complete the table in the Printed Answer Booklet, starting a new row each time that STEP 3 or STEP 7 is used.\\
You should not need all the lines in the Answer Booklet.
Becky measures the efficiency of her sort by counting using the number of times that STEP 3 is used.
\item \begin{enumerate}[label=(\roman*)]
\item How many times did Becky use STEP 3 in sorting the list from part (b)?
\item What is the greatest number of times that STEP 3 could be used in sorting a list of 6 values?
A computer takes 15 seconds to sort a list of 60 numbers using Becky's algorithm.
\end{enumerate}\item Approximately how long would you expect it to take the computer to sort a list of 300 numbers using the algorithm?
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2019 Q3 [11]}}