| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Comparing Sorting Algorithms |
| Difficulty | Easy -1.8 This is a routine algorithmic execution question requiring only mechanical application of bubble sort and shuttle sort procedures learned directly from the syllabus. The calculations are straightforward (counting comparisons/swaps, applying quadratic scaling), with no problem-solving, proof, or novel insight required—purely procedural recall and execution. |
| Spec | 7.03g Order notation: O(n^k) for k = 0,1,2,3,47.03j Sorting: bubble sort and shuttle sort |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Comparisons: 31&28, 28&75, 75&87, 87&42, 42&43, 43&70, 70&56, 56&61, 61&95 | B1 | 9 comparisons stated |
| Result: 28 31 75 87 42 43 70 56 61 95 → 28 31 75 42 43 70 56 61 87 95 → ... showing swaps | M1 | Working through pass |
| 9 comparisons, swaps shown correctly | A1 | |
| 95 is guaranteed in correct final position (last) | B1 | Must identify 95 specifically |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| 28 31 42 43 70 56 61 75 87 95 | B1 | ft from (a) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| 7 more passes | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Pass 1: compare 31&28, swap → 28 31 75 87 42 43 70 56 61 95; 1 comparison, 1 swap | B1 | |
| Pass 2: compare 75&31, no swap; compare 75&28, no swap → 28 31 75 87 42 43 70 56 61 95; 2 comparisons, 0 swaps | B1 B1 B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Bubble sort always makes 9 comparisons on first pass (and continues through all passes) | M1 | |
| Shuttle sort stops early when no swap needed, so fewer comparisons overall (e.g. pass 2 only needs 2 comparisons not 9) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(\frac{50^2}{10^2} \times 20 = 25 \times 20 = 500\) seconds | M1 A1 | Use of \(n^2\) scaling; M1 for \(\left(\frac{50}{10}\right)^2\), A1 for 500 |
# Question 1:
## Part (i)(a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Comparisons: 31&28, 28&75, 75&87, 87&42, 42&43, 43&70, 70&56, 56&61, 61&95 | B1 | 9 comparisons stated |
| Result: 28 31 75 87 42 43 70 56 61 95 → 28 31 75 42 43 70 56 61 87 95 → ... showing swaps | M1 | Working through pass |
| 9 comparisons, swaps shown correctly | A1 | |
| 95 is guaranteed in correct final position (last) | B1 | Must identify 95 specifically |
## Part (i)(b)
| Answer | Mark | Guidance |
|--------|------|----------|
| 28 31 42 43 70 56 61 75 87 95 | B1 | ft from (a) |
## Part (i)(c)
| Answer | Mark | Guidance |
|--------|------|----------|
| 7 more passes | B1 | |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Pass 1: compare 31&28, swap → 28 31 75 87 42 43 70 56 61 95; 1 comparison, 1 swap | B1 | |
| Pass 2: compare 75&31, no swap; compare 75&28, no swap → 28 31 75 87 42 43 70 56 61 95; 2 comparisons, 0 swaps | B1 B1 B1 | |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Bubble sort always makes 9 comparisons on first pass (and continues through all passes) | M1 | |
| Shuttle sort stops early when no swap needed, so fewer comparisons overall (e.g. pass 2 only needs 2 comparisons not 9) | A1 | |
## Part (iv)
| Answer | Mark | Guidance |
|--------|------|----------|
| $\frac{50^2}{10^2} \times 20 = 25 \times 20 = 500$ seconds | M1 A1 | Use of $n^2$ scaling; M1 for $\left(\frac{50}{10}\right)^2$, A1 for 500 |
---1 Owen and Hari each want to sort the following list of marks into decreasing order.
$$\begin{array} { l l l l l l l l l l }
31 & 28 & 75 & 87 & 42 & 43 & 70 & 56 & 61 & 95
\end{array}$$
(i) Owen uses bubble sort, starting from the left-hand end of the list.
\begin{enumerate}[label=(\alph*)]
\item Show the result of the first pass through the list. Record the number of comparisons and the number of swaps used in this first pass. Which marks, if any, are guaranteed to be in their correct final positions after the first pass?
\item Write down the list at the end of the second pass of bubble sort.
\item How many more passes are needed to get the value 95 to the start of the list?\\
(ii) Hari uses shuttle sort, starting from the left-hand end of the list.
Show the results of the first and the second pass through the list. Record the number of comparisons and the number of swaps used in each of these passes.\\
(iii) Explain why, for this particular list, the total number of comparisons will be greater using bubble sort than using shuttle sort.
Shuttle sort is a quadratic order algorithm.\\
(iv) If it takes Hari 20 seconds to sort a list of ten marks using shuttle sort, approximately how long will it take Hari to sort a list of fifty marks?
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2010 Q1 [14]}}