| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 18 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Bubble Sort Execution |
| Difficulty | Easy -1.2 This is a routine algorithmic execution question requiring mechanical application of bubble sort and shuttle sort to small lists (8 elements each), followed by straightforward complexity calculations. While multi-part with several marks, it demands only procedural recall and arithmetic—no problem-solving insight or novel reasoning is needed, making it easier than average A-level questions. |
| Spec | 7.03d Order of algorithm: dominant term and scaling run-times7.03e Efficiency comparison: of two algorithms on specific cases7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort |
| Answer | Marks |
|---|---|
| M1 | nb decreasing or numbers misread ⟹ M only; For result of first pass correct (underlined entries may be omitted) |
| Answer | Marks |
|---|---|
| M1 | For second and third passes correct, must be using bubble sort |
| M1 | For fourth and fifth passes correct, must be using bubble sort |
| A1 | For sixth pass correct, from correct method |
| B1 | For 15, from correct method |
| B1 (6) | For 27, from correct method |
| Answer | Marks |
|---|---|
| M1 | nb decreasing or numbers misread ⟹ M only; For result of first pass correct (underlined entries may be omitted) |
| Answer | Marks |
|---|---|
| M1 | For second and third passes correct, must be using shuttle sort |
| M1 | For fourth and fifth passes correct, must be using shuttle sort |
| A1 | For seventh pass correct, from correct method |
| B1 | For 21, from correct method |
| B1 (6) | For 25, from correct method |
| Answer | Marks |
|---|---|
| B1 | For 'each script is looked at once', or equivalent |
| B1 | For 'proportional', or equivalent |
| (2) |
| Answer | Marks |
|---|---|
| M1 | 250 (but not for \(250 + 50\)) |
| Answer | Marks |
|---|---|
| M1 | \((500÷2)^2\), \((250)^2\), \((100÷2)^2\) or equivalent |
| A1 (4) | For 6250, dependent on previous M only |
Total = 6500 seconds or 108 minutes 20 seconds
| Answer | Marks |
|---|---|
| A1 | For 6500 or equivalent |
| \(\mathbf{18}\) |
**(i)** Original list: 34 42 27 31 12 48 24 37
1st pass: 34 27 31 12 42 24 37 48
| M1 | nb decreasing or numbers misread ⟹ M only; For result of first pass correct (underlined entries may be omitted) |
2nd pass: 27 31 12 34 24 37 42 48
3rd pass: 27 12 31 24 34 37 42 48
4th pass: 12 27 24 31 34 37 42 48
5th pass: 12 24 27 31 34 37 42 48
6th pass: 12 24 27 31 34 37 42 48
| M1 | For second and third passes correct, must be using bubble sort |
| M1 | For fourth and fifth passes correct, must be using bubble sort |
| A1 | For sixth pass correct, from correct method |
| B1 | For 15, from correct method |
| B1 (6) | For 27, from correct method |
Swaps = $5+5+2+2+1 = 15$
Comparisons = $7+6+5+4+3+2 = 27$
**(ii)** Original list: 95 74 61 87 71 82 53 57
1st pass: 74 95 61 87 71 82 53 57
| M1 | nb decreasing or numbers misread ⟹ M only; For result of first pass correct (underlined entries may be omitted) |
2nd pass: 61 74 95 87 71 82 53 57
3rd pass: 61 74 87 95 71 82 53 57
4th pass: 61 71 74 87 95 82 53 57
5th pass: 61 71 74 82 87 95 53 57
6th pass: 53 61 71 74 82 87 95 57
7th pass: 53 57 61 71 74 82 87 95
| M1 | For second and third passes correct, must be using shuttle sort |
| M1 | For fourth and fifth passes correct, must be using shuttle sort |
| A1 | For seventh pass correct, from correct method |
| B1 | For 21, from correct method |
| B1 (6) | For 25, from correct method |
Swaps = $1+2+1+3+2+6+6 = 21$
Comparisons = $1+2+2+4+3+6+7 = 25$
**(iii)** Each script is looked at once so the time taken is roughly proportional to the number of scripts
| B1 | For 'each script is looked at once', or equivalent |
| B1 | For 'proportional', or equivalent |
| | (2) |
**(iv)** Splitting 100 scripts takes 50 seconds so splitting 500 scripts takes about 250 seconds
| M1 | 250 (but not for $250 + 50$) |
Sorting 50 scripts takes 250 seconds = $0.1 \times 50^2$
Sorting 250 scripts takes about $0.1 \times 250^2 = 6250$ seconds
| M1 | $(500÷2)^2$, $(250)^2$, $(100÷2)^2$ or equivalent |
| A1 (4) | For 6250, dependent on previous M only |
Total = 6500 seconds or 108 minutes 20 seconds
| A1 | For 6500 or equivalent |
| | $\mathbf{18}$ |7 Mr Rank and Miss File need to sort a pile of examination scripts into increasing order of mark. Mr Rank first goes through the pile of scripts and puts each script into one of two piles, depending on whether the mark is below 50 or not. He then sorts the scripts in the 'below 50 ' pile and Miss File sorts the scripts in the '50 and above' pile. At the end they put the two sorted piles together again.\\
(i) The scripts in the 'below 50' pile have the following marks, starting from the top of the pile.
$$\begin{array} { l l l l l l l l }
34 & 42 & 27 & 31 & 12 & 48 & 24 & 37
\end{array}$$
Use bubble sort to sort this list into increasing order. Clearly indicate the list that results at the end of each pass through the algorithm. Give the number of swaps and the number of comparisons that were used in sorting this list.\\
(ii) The scripts in the '50 and above' pile have the following marks, starting from the top of the pile.
$$\begin{array} { l l l l l l l l }
95 & 74 & 61 & 87 & 71 & 82 & 53 & 57
\end{array}$$
Use shuttle sort to sort this list into increasing order. Clearly indicate the list that results at the end of each pass through the algorithm. List the number of swaps and number of comparisons that were used in sorting this list.\\
(iii) Explain why splitting the original list into two piles is a linear order algorithm.\\
(iv) Both bubble sort and shuttle sort are quadratic order algorithms. Mr Rank and Miss File use their method to sort a pile of 100 scripts. It takes about 50 seconds to split the pile and about 250 seconds to do each sort. As the sorts are done at the same time, this gives a total time taken of about 300 seconds, or 6 minutes. Approximately how long would Mr Rank and Miss File take to split a pile of 500 scripts into two roughly equal piles and sort the piles? Show all your working.\\[0pt]
[4]
\hfill \mbox{\textit{OCR D1 2006 Q7 [18]}}