| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2023 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Comparing Sorting Algorithms |
| Difficulty | Easy -1.2 This is a routine algorithmic execution question requiring mechanical application of two standard sorting algorithms with no problem-solving or insight. Students simply follow learned procedures step-by-step, count operations, and recall the meaning of O(n²) notation—all standard textbook exercises for this topic. |
| Spec | 7.03g Order notation: O(n^k) for k = 0,1,2,3,47.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort |
| Answer | Marks |
|---|---|
| 3 | 4 |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | 7 | |
| 3 | (a) | (i) |
| Answer | Marks |
|---|---|
| Fourth pass 7 10 18 23 31 54 62 82 | M1 |
| Answer | Marks |
|---|---|
| [3] | 1.1 |
| Answer | Marks |
|---|---|
| 1.1 | Bubble increasing |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (a) | (ii) |
| Answer | Marks |
|---|---|
| Fourth pass = 0 | M1 |
| Answer | Marks |
|---|---|
| [2] | 1.1 |
| 1.1 | 5 swaps in first pass (allow FT provided M1 gained in (a)(i)) |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (b) | (i) |
| Answer | Marks |
|---|---|
| Seventh pass 7 10 18 23 31 54 62 82 | M1 |
| Answer | Marks |
|---|---|
| [3] | 1.1 |
| Answer | Marks |
|---|---|
| 1.1 | Shuttle increasing |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (b) | (ii) |
| Fifth = 1, sixth = 2, seventh = 0 | M1 |
| Answer | Marks |
|---|---|
| [2] | 1.1 |
| 1.1 | Number of swaps correct for first four passes (allow FT provided |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (c) | E.g. Both use 8 swaps but shuttle sort uses |
| fewer comparisons so is more efficient | B1 | |
| [1] | 3.1a | Fewer comparisons or smaller total (from valid reasoning and |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (d) | E.g. Takes (approximately) 9 times as long |
| [1] | 2.2a | 2 |
Question 3:
3 | 4
3
3 | 7
3 | (a) | (i) | First pass 10 18 7 23 54 31 62 (82)
Second pass 10 7 18 23 31 54 (62 82)
Third pass 7 10 18 23 31 (54 62 82)
Fourth pass 7 10 18 23 31 54 62 82 | M1
A1
A1
[3] | 1.1
1.1
1.1 | Bubble increasing
Result at end of first pass starts 10 18 7 …
Results correct at end of first, second and third passes (cao)
A final fourth pass in which nothing changes
Allow at most one misread for max M1 A0 A1
Decreasing: first pass starts 23 18 10 … M1 A0 A0
3 | (a) | (ii) | First = 5
Second = 2, third = 1
Fourth pass = 0 | M1
A1
[2] | 1.1
1.1 | 5 swaps in first pass (allow FT provided M1 gained in (a)(i))
2 swaps in second pass and 1 swap in third pass (cao)
Ignore swaps for fourth pass (and any others that are shown)
Swaps must be written in figures (not tallies)
3 | (b) | (i) | First pass 10 23 18 7 62 54 31 82
Second pass 10 18 23 (7 62 54 31 82)
Third pass 7 10 18 23 (62 54 31 82)
Fourth pass 7 10 18 23 62 (54 31 82)
Fifth pass 7 10 18 23 54 62 (31 82)
Sixth pass 7 10 18 23 31 54 62 (82)
Seventh pass 7 10 18 23 31 54 62 82 | M1
A1
A1
[3] | 1.1
1.1
1.1 | Shuttle increasing
Result at end of first pass starts 10 23
Results correct at end of second, third and fourth passes (cao)
Results correct at end of fifth, sixth and seventh passes (cao)
Seven passes used in total
Allow at most one misread for max M1 A1 A0
Decreasing: first pass starts 23 10 with 0 swaps M1 A0 A0
3 | (b) | (ii) | First = 1, second = 1, third = 3, fourth = 0
Fifth = 1, sixth = 2, seventh = 0 | M1
A1
[2] | 1.1
1.1 | Number of swaps correct for first four passes (allow FT provided
M1 gained in (b)(i) and consistently increasing, or decreasing)
All correct, with exactly 7 passes used
Swaps must be written in figures (not tallies
3 | (c) | E.g. Both use 8 swaps but shuttle sort uses
fewer comparisons so is more efficient | B1
[1] | 3.1a | Fewer comparisons or smaller total (from valid reasoning and
increasing)
Number of comparisons need not be evaluated (or be correct)
(bubble = 7+6+5+4 = 22, shuttle = 1+2+3+1+2+3+1=13)
but shuttle sort must have fewer comparisons than bubble sort
(their) 13 < (their) 22 or (their) 21 < (their) 30
Not using ratios
3 | (d) | E.g. Takes (approximately) 9 times as long | B1
[1] | 2.2a | 2
32 or 9 seen in context, (3000) = 9 (so run time is) 9 times as long
1000
Allow ‘increase by 9’ (BOD scale factor), allow 9
‘exponential’ B0 unless 9 (o.e.) also seen3 The list of numbers below is to be sorted into increasing order.\\
$\begin{array} { l l l l l l l l } 23 & 10 & 18 & 7 & 62 & 54 & 31 & 82 \end{array}$
\begin{enumerate}[label=(\alph*)]
\item Sort the list using bubble sort.
You do not need to show intermediate working.
\begin{enumerate}[label=(\roman*)]
\item Record the list that results at the end of each pass.
\item Record the number of swaps used in each pass.
\end{enumerate}\item Now sort the original list using shuttle sort.
You do not need to show intermediate working.
\begin{enumerate}[label=(\roman*)]
\item Record the list that results at the end of each pass.
\item Record the number of swaps used in each pass.
\end{enumerate}\item Using the total number of comparisons plus the total number of swaps as a measure of efficiency, explain why shuttle sort is more efficient than bubble sort for sorting this particular list.
Bubble sort and shuttle sort are both $\mathrm { O } \left( n ^ { 2 } \right)$.
\item Explain what this means for the run-time of the algorithms when the length of the list being sorted changes from 1000 to 3000.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2023 Q3 [12]}}