| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Bubble Sort Execution |
| Difficulty | Easy -1.8 This is a purely mechanical execution of bubble sort algorithm requiring only rote application of a memorized procedure with no problem-solving, insight, or mathematical reasoning. Students simply follow the algorithm step-by-step on a short 6-element list, making it significantly easier than typical A-level questions that require conceptual understanding or multi-step reasoning. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Original list: 24 57 9 31 16 4 | ||
| Compare 24 and 57; or 24 57 9 31 16 4 | M1 | Values compared and values swapped written down or indicated using underlining and/or arrows. Must be immediately obvious which values are being compared |
| Compare 57 and 9, swap; 24 57 9 31 16 4 | ||
| Compare 57 and 31, swap; 24 9 57 31 16 4 | ||
| Compare 57 and 16, swap; 24 9 31 57 16 4 | ||
| Compare 57 and 4, swap; 24 9 31 16 57 4 | ||
| Resulting list: 24 9 31 16 4 57 | A1 | List correct (written) after one pass. List without showing which values are compared and which are swapped \(\Rightarrow\) M0, A0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 9 24 16 4 31 57 | B1 | cao, allow 9 24 16 4 \ |
| 9 16 4 24 31 57 | B1 | cao, allow 9 16 4 \ |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Five non-negative integer values (being at maximum 5, 4, 3, 2, 1 respectively) | M1 | |
| 4, 3, 2, 1, 1 | A1 | cao (ignore 11 if seen as total) |
# Question 1:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Original list: 24 57 9 31 16 4 | | |
| Compare 24 and 57; or 24 57 9 31 16 4 | M1 | Values compared and values swapped written down or indicated using underlining and/or arrows. Must be immediately obvious which values are being compared |
| Compare 57 and 9, swap; 24 57 9 31 16 4 | | |
| Compare 57 and 31, swap; 24 9 57 31 16 4 | | |
| Compare 57 and 16, swap; 24 9 31 57 16 4 | | |
| Compare 57 and 4, swap; 24 9 31 16 57 4 | | |
| Resulting list: 24 9 31 16 4 57 | A1 | List correct (written) after one pass. List without showing which values are compared and which are swapped $\Rightarrow$ M0, A0 |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| 9 24 16 4 31 57 | B1 | cao, allow 9 24 16 4 \| 31 57, but not just 9 24 16 4 |
| 9 16 4 24 31 57 | B1 | cao, allow 9 16 4 \| 24 31 57, but not just 9 16 4. Penalise each new miscopy of their own work by 1 mark (up to maximum of 2) |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Five non-negative integer values (being at maximum 5, 4, 3, 2, 1 respectively) | M1 | |
| 4, 3, 2, 1, 1 | A1 | cao (ignore 11 if seen as total) |
---1 The list below is to be sorted into increasing order using bubble sort, starting at the left-hand end of the list.
$$\begin{array} { l l l l l l }
24 & 57 & 9 & 31 & 16 & 4
\end{array}$$
(i) Show which values are compared and which are swapped in the first pass. Write down the list that results at the end of the first pass.\\
(ii) Without showing the individual comparisons and swaps, write down the lists that result after the second pass and after the third pass.\\
(iii) In total there will be five passes made in carrying out bubble sort on the list. Write down how many swaps are made in each pass.
\hfill \mbox{\textit{OCR D1 2013 Q1 [6]}}