| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2022 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Comparing Sorting Algorithms |
| Difficulty | Easy -1.8 This is a purely procedural question requiring mechanical application of two standard sorting algorithms with no problem-solving, insight, or mathematical reasoning. Students simply execute memorized algorithms step-by-step and count operations—significantly easier than typical A-level questions that require understanding or novel application of concepts. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| First pass: 38 15 52 27 49 10 33 61 74 96 | M1 | First pass of bubble sort correct, condone starting from RHS and/or decreasing |
| Second pass: 15 38 27 49 10 33 52 61 74 96 | A1 | Correct list at end of second and third passes (increasing starting from LHS) may imply fixed values |
| Third pass: 15 27 38 10 33 49 52 61 74 96 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| First pass: Comparisons = 9, Swaps = 7 | B1 | Comparisons correct |
| Second pass: Comparisons = 8, Swaps = 5 | B1 | Swaps correct |
| Third pass: Comparisons = 7, Swaps = 3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| First pass: 38 52 15 61 27 49 10 33 96 74 | M1 | First pass of shuttle sort correct, condone starting from RHS and/or decreasing, may imply fixed values |
| Second pass: 15 38 52 61 27 49 10 33 96 74 | A1 | Correct list at end of second and third passes, may imply fixed values |
| Third pass: 15 38 52 61 27 49 10 33 96 74 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| First pass: Comparisons = 1, Swaps = 1 | B1 | Comparisons correct |
| Second pass: Comparisons = 2, Swaps = 2 | B1 | Swaps correct |
| Third pass: Comparisons = 1, Swaps = 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Fewer comparisons and fewer swaps for shuttle | M1 FT | Compare comparisons and compare swaps (in words or numerically) |
| Shuttle sort is more efficient than bubble sort for the first three passes of this list | A1 FT | Shuttle more efficient, or bubble less efficient (at this stage). Follow through their values from (a)(ii) and (b)(ii) |
# Question 3:
## Part (a)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| First pass: **38 15 52 27 49 10 33 61 74 96** | M1 | First pass of bubble sort correct, condone starting from RHS and/or decreasing |
| Second pass: **15 38 27 49 10 33 52 61 74** 96 | A1 | Correct list at end of second and third passes (increasing starting from LHS) may imply fixed values |
| Third pass: **15 27 38 10 33 49 52 61** 74 96 | | |
## Part (a)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| First pass: Comparisons = 9, Swaps = 7 | B1 | Comparisons correct |
| Second pass: Comparisons = 8, Swaps = 5 | B1 | Swaps correct |
| Third pass: Comparisons = 7, Swaps = 3 | | |
## Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| First pass: **38 52** 15 61 27 49 10 33 96 74 | M1 | First pass of shuttle sort correct, condone starting from RHS and/or decreasing, may imply fixed values |
| Second pass: **15 38 52** 61 27 49 10 33 96 74 | A1 | Correct list at end of second and third passes, may imply fixed values |
| Third pass: **15 38 52 61** 27 49 10 33 96 74 | | |
## Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| First pass: Comparisons = 1, Swaps = 1 | B1 | Comparisons correct |
| Second pass: Comparisons = 2, Swaps = 2 | B1 | Swaps correct |
| Third pass: Comparisons = 1, Swaps = 0 | | |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Fewer comparisons and fewer swaps for shuttle | M1 FT | Compare comparisons and compare swaps (in words or numerically) |
| Shuttle sort is more efficient than bubble sort for the first three passes of this list | A1 FT | Shuttle more efficient, or bubble less efficient (at this stage). Follow through their values from (a)(ii) and (b)(ii) |
---3
\begin{enumerate}[label=(\alph*)]
\item The list below is to be sorted into increasing order using bubble sort.\\
$\begin{array} { l l l l l l l l l l } 52 & 38 & 15 & 61 & 27 & 49 & 10 & 33 & 96 & 74 \end{array}$
\begin{enumerate}[label=(\roman*)]
\item Determine the list that results at the end of the first, second and third passes. You do not need to show the individual swaps in each pass.
\item Write down the number of comparisons and the number of swaps used in each of these passes.
\end{enumerate}\item The list below is to be sorted into increasing order using shuttle sort.\\
$\begin{array} { l l l l l l l l l l } 52 & 38 & 15 & 61 & 27 & 49 & 10 & 33 & 96 & 74 \end{array}$
\begin{enumerate}[label=(\roman*)]
\item Determine the list that results at the end of the first, second and third passes. You do not need to show the individual swaps in each pass.
\item Write down the number of comparisons and the number of swaps used in each of these passes.
\end{enumerate}\item Use the results from parts (a) and (b) to compare the efficiency of bubble sort with the efficiency of shuttle sort for the first three passes of this list. You do not need to consider what happens after these three passes.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2022 Q3 [10]}}