| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Shuttle Sort Execution |
| Difficulty | Easy -1.8 This is a straightforward algorithmic execution question requiring only careful following of given instructions with no problem-solving, insight, or understanding of why the algorithms work. Students simply trace through predetermined steps with a small dataset (5 numbers), recording comparisons and swaps mechanically. |
| Spec | 7.03b Algorithm awareness: uses and practical limitations7.03j Sorting: bubble sort and shuttle sort |
| Answer | Marks | Guidance |
|---|---|---|
| (i) | After 1st pass: \(6 \; 8 \; 9 \; 7 \; 5\) Comps 1, Swaps 1 After 2nd pass: \(6 \; 8 \; 9 \; 7 \; 5\) 1, 0 After 3rd pass: \(6 \; 7 \; 8 \; 9 \; 5\) 3, 2 After 4th pass: \(5 \; 6 \; 7 \; 8 \; 9\) 4, 4 | M1, M1, M1, A1 |
| Comparisons must be 1, 2, 3 or 4 with total \(\leq 10\) Swaps must be 0, 1, 2, 3 or 4 and no more than corresponding number of comparisons | B1, B1 | Counting comparisons for at least three passes Counting swaps for at least three passes |
| (ii) | Step 1 \(A = 8 \; 6 \; 9 \; 7 \; 5\) | |
| Step 2 \(A = 6 \; 9 \; 7 \; 5\) \(X = 8\) | M1 | For identifying that \(6 \to B\) or the sublist \(\{6\}\) |
| Step 3 \(A = 9 \; 7 \; 5\) \(B = 6 \; 8\) | M1 | For identifying that \(9 \to C\) or the sublist \(\{9\}\) |
| Step 4 \(A = 7 \; 5\) \(C = 9\) | M1 | For identifying that \(7 \to B\) |
| Step 4 \(A = 5\) \(B = 6 \; 7 \; 8\) | M1 | For identifying that \(5 \to B\) |
| Step 6 \(N = 3\) | ||
| Step 7 \(A = 6 \; 7 \; 5 \; 8 \; 9\) | A1, 5 | For the final A list or the display correct [11] |
(i) | After 1st pass: $6 \; 8 \; 9 \; 7 \; 5$ Comps 1, Swaps 1 After 2nd pass: $6 \; 8 \; 9 \; 7 \; 5$ 1, 0 After 3rd pass: $6 \; 7 \; 8 \; 9 \; 5$ 3, 2 After 4th pass: $5 \; 6 \; 7 \; 8 \; 9$ 4, 4 | M1, M1, M1, A1 | Bubble sort or decreasing order loses first 4 marks 1st pass correct 2nd pass correct, follow through from 1st pass 3rd pass correct, follow through from 2nd pass 4th pass correct
| Comparisons must be 1, 2, 3 or 4 with total $\leq 10$ Swaps must be 0, 1, 2, 3 or 4 and no more than corresponding number of comparisons | B1, B1 | Counting comparisons for at least three passes Counting swaps for at least three passes
(ii) | Step 1 $A = 8 \; 6 \; 9 \; 7 \; 5$ | |
| Step 2 $A = 6 \; 9 \; 7 \; 5$ $X = 8$ | M1 | For identifying that $6 \to B$ or the sublist $\{6\}$
| Step 3 $A = 9 \; 7 \; 5$ $B = 6 \; 8$ | M1 | For identifying that $9 \to C$ or the sublist $\{9\}$
| Step 4 $A = 7 \; 5$ $C = 9$ | M1 | For identifying that $7 \to B$
| Step 4 $A = 5$ $B = 6 \; 7 \; 8$ | M1 | For identifying that $5 \to B$
| Step 6 $N = 3$ | |
| Step 7 $A = 6 \; 7 \; 5 \; 8 \; 9$ | A1, 5 | For the final A list or the display correct [11]
---3 (i) Use shuttle sort to sort the five numbers 8, 6, 9, 7, 5 into increasing order. Write down the list that results at the end of each pass. Calculate and record the number of comparisons and the number of swaps that are made in each pass.\\
(ii) The algorithm below is part of another method for sorting a list into increasing order. A pply it to the list 8, 6, 9, 7, 5. Show the result of each step.
Step 1: Input the original list and call it list A.\\
Step 2: Remove the first item in list $A$ and call this item $X$.\\
Step 3: If the first item remaining in list A is less than X move it to list B , otherwise move it to list C.\\
Step 4: If the next item remaining in list A is less than X move it to become the next item in list B, otherwise move it to become the next item in list C.\\
Step 5: If there are still items in list A, repeat Step 4.\\
Step 6: Count the number of items in list $\mathbf { B }$ and call this $\mathbf { N }$.\\
Step 7: Put the items in list B at positions 1 to N of list A, item X at position $\mathrm { N } + 1$ of list A and the items in list C at positions $\mathrm { N } + 2$ onwards of list A.\\
Step 8: Display list A.
\hfill \mbox{\textit{OCR D1 2007 Q3 [11]}}