| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | January |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Quick Sort Execution |
| Difficulty | Easy -1.2 This is a straightforward algorithmic execution question requiring mechanical application of standard D1 algorithms (bubble sort, quick sort, bin packing) with no problem-solving or insight needed. The procedures are entirely routine and follow textbook steps exactly, making it easier than average A-level maths questions which typically require some mathematical reasoning. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Bin 1: 1.1 0.7 0.9 0.2 Bin 2: 1.9 0.4 0.5 Bin 3: 2.1 Bin 4: 2.3 Bin 5: 1.7 | M1 A1 A1 (3) | |
| 1.1 1.9 0.9 2.1 0.7 2.3 0.4 0.5 1.7 0.2 | M1 A1 | |
| Comparisons: 9 Swaps: 7 | B1 B1 (4) | |
| e.g. using middle right 1.9 1.1 2.1 0.9 2.3 0.7 0.5 1.7 0.4 0.2 pivot 0.7 1.9 1.1 2.1 0.9 1.7 0.7 0.5 0.4 0.2 pivot(s) 0.9 0.4 2.3 1.1 2.1 1.7 0.9 0.7 0.5 0.4 0.2 pivot(s) (2.3) 1.1 2.3 2.1 1.9 0.7 0.9 0.7 0.5 0.4 0.2 pivot(s) 1.7 2.3 2.1 1.9 0.9 0.7 0.5 0.4 0.2 (sort complete) | M1 A1 A1ft A1 (4) | |
| Bin 1: 2.3 0.7 Bin 2: 2.1 0.9 Bin 3: 1.9 1.1 Bin 4: 1.7 0.5 0.4 0.2 | M1 A1 A1 (3) | |
| 14 marks |
| Answer | Marks | Guidance |
|---|---|---|
| Working | Marks | Guidance |
| 1.9 1.1 2.1 0.9 2.3 0.7 0.5 1.7 0.4 0.2 Pivot 2.3 | M1 A1 | |
| 2.3 1.9 1.1 2.1 0.9 0.7 0.5 1.7 0.4 0.2 Pivot 0.7 | A1ft | |
| 2.3 1.9 1.1 2.1 0.9 1.7 0.7 0.5 0.4 0.2 Pivot 2.1 (0.5) (0.2) | A1ft | |
| 2.3 2.1 1.9 1.1 0.9 1.7 0.7 0.5 0.4 0.2 Pivot 1.1 (0.9) 1.9 1.7 0.7 0.5 0.4 0.2 (sort complete) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Working | Marks | Guidance |
| 1.9 1.1 2.1 0.9 2.3 0.7 0.5 1.7 0.4 0.2 Pivot 0.7 | M1 A1 | |
| 0.5 0.4 0.2 0.7 1.9 1.1 2.1 0.9 2.3 1.7 Pivot 0.4 0.9 | A1ft | |
| 0.2 0.4 0.5 0.7 0.9 1.9 1.1 2.1 2.3 1.7 Pivot (0.2) (0.5) 2.1 | A1ft | |
| 0.2 0.4 0.5 0.7 0.9 1.9 1.1 2.1 2.3 1.7 1.7 2.1 2.3 sort complete | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Working | Marks | Guidance |
| 1.9 1.1 2.1 0.9 2.3 0.7 0.5 1.7 0.4 0.2 Pivot 2.3 | M1 A1 | |
| 1.9 1.1 2.1 0.9 0.7 0.5 1.7 0.4 0.2 2.3 Pivot 0.7 | A1ft | |
| 0.5 0.4 0.2 0.7 1.9 1.1 2.1 0.9 1.7 2.3 Pivot 0.4 2.1 | A1ft | |
| 0.2 0.4 0.5 0.7 1.9 1.1 2.1 0.9 1.7 2.3 Pivot (0.2) (0.5) 1.1 sort complete | A1 |
| Answer | Marks | Guidance |
|--------|-------|----------|
| Bin 1: 1.1 0.7 0.9 0.2 Bin 2: 1.9 0.4 0.5 Bin 3: 2.1 Bin 4: 2.3 Bin 5: 1.7 | M1 A1 A1 (3) | |
| 1.1 1.9 0.9 2.1 0.7 2.3 0.4 0.5 1.7 0.2 | M1 A1 | |
| Comparisons: 9 Swaps: 7 | B1 B1 (4) | |
| e.g. using middle right 1.9 1.1 2.1 0.9 2.3 0.7 0.5 1.7 0.4 0.2 pivot 0.7 1.9 1.1 2.1 0.9 1.7 0.7 0.5 0.4 0.2 pivot(s) 0.9 0.4 2.3 1.1 2.1 1.7 0.9 0.7 0.5 0.4 0.2 pivot(s) (2.3) 1.1 2.3 2.1 1.9 0.7 0.9 0.7 0.5 0.4 0.2 pivot(s) 1.7 2.3 2.1 1.9 0.9 0.7 0.5 0.4 0.2 (sort complete) | M1 A1 A1ft A1 (4) | |
| Bin 1: 2.3 0.7 Bin 2: 2.1 0.9 Bin 3: 1.9 1.1 Bin 4: 1.7 0.5 0.4 0.2 | M1 A1 A1 (3) | |
| | 14 marks | |
**Notes for Question 3:**
- a1M1: First four numbers placed correctly and at least six numbers put in bins. Condone cumulative totals here only.
- a1A1: First seven numbers placed correctly.
- a2A1: CSO – all correct.
- bi1M1: Bubble sort, end number in place correctly.
- SC for M1 only: 0.7 1.1 0.9 1.9 0.2 2.1 0.4 0.5 1.7 2.3 (ascending from left-hand end). 0.2 1.1 0.7 1.9 0.9 2.1 0.4 2.3 0.5 1.7 (ascending from right-hand end). 2.3 1.1 0.7 1.9 0.9 2.1 0.2 1.7 0.4 0.5 (descending from right-hand end).
- bi1A1: CAO – isw after one complete pass.
- bii1B1: Comparisons correct (9).
- bii2B1: Swaps correct (7).
- c1M1: Quick sort – pivots, p. selected and first pass gives >p, p, <p. **If only choosing 1 pivot per iteration M1 only. Using bubble sort in this part is M0.**
- c1A1: First pass correct and next pivots chosen correctly/consistently for second pass.
- c2A1ft: Second and third passes correct (follow through from their first pass and choice of pivots) – next pivot(s) chosen correctly/consistently for fourth pass.
- c3A1: CSO – including choice of pivot for the fifth pass and then either a 'stop' statement or final re-listing or using each item as a pivot.
- d1M1: Must be using 'sorted' list in decreasing order (independent of (c)). First five numbers placed correctly and at least six numbers put in bins. **First-fit increasing is M0.**
- d1A1: First seven numbers placed correctly.
- d2A1: CSO – all correct.
**SC for (d): If the 'sorted' list used in (d) has one 'error' from (c) (e.g. a missing number, an extra number or one number incorrectly placed) then M1 only can be awarded in (d) (for the first five numbers placed correctly). If there is more than one 'error' then M0. Allow full marks in (d) if a correct list is used in (d) even if the list is incorrect at the end of (c).**
**Sorting list into ascending order in (c):**
- If the candidate sorts the list into ascending order and reverses the list in (c) then they can score full marks in (c).
- If the list is not reversed in (c) then mark as a misread (so remove the last two A marks earned in (c)). If the list is reversed at the start of (d) but not in (c) then still treat this as a misread. If the candidate says that the list needs reversing in (c) but doesn't actually show the reversed list in (c) then remove the final A mark earned in (c).
**Middle left:**
| Working | Marks | Guidance |
|---------|-------|----------|
| 1.9 1.1 2.1 0.9 2.3 0.7 0.5 1.7 0.4 0.2 Pivot 2.3 | M1 A1 | |
| 2.3 1.9 1.1 2.1 0.9 0.7 0.5 1.7 0.4 0.2 Pivot 0.7 | A1ft | |
| 2.3 1.9 1.1 2.1 0.9 1.7 0.7 0.5 0.4 0.2 Pivot 2.1 (0.5) (0.2) | A1ft | |
| 2.3 2.1 1.9 1.1 0.9 1.7 0.7 0.5 0.4 0.2 Pivot 1.1 (0.9) 1.9 1.7 0.7 0.5 0.4 0.2 (sort complete) | A1 | |
**Ascending order (middle right):**
| Working | Marks | Guidance |
|---------|-------|----------|
| 1.9 1.1 2.1 0.9 2.3 0.7 0.5 1.7 0.4 0.2 Pivot 0.7 | M1 A1 | |
| 0.5 0.4 0.2 0.7 1.9 1.1 2.1 0.9 2.3 1.7 Pivot 0.4 0.9 | A1ft | |
| 0.2 0.4 0.5 0.7 0.9 1.9 1.1 2.1 2.3 1.7 Pivot (0.2) (0.5) 2.1 | A1ft | |
| 0.2 0.4 0.5 0.7 0.9 1.9 1.1 2.1 2.3 1.7 1.7 2.1 2.3 sort complete | A1 | |
**Ascending order (middle left):**
| Working | Marks | Guidance |
|---------|-------|----------|
| 1.9 1.1 2.1 0.9 2.3 0.7 0.5 1.7 0.4 0.2 Pivot 2.3 | M1 A1 | |
| 1.9 1.1 2.1 0.9 0.7 0.5 1.7 0.4 0.2 2.3 Pivot 0.7 | A1ft | |
| 0.5 0.4 0.2 0.7 1.9 1.1 2.1 0.9 1.7 2.3 Pivot 0.4 2.1 | A1ft | |
| 0.2 0.4 0.5 0.7 1.9 1.1 2.1 0.9 1.7 2.3 Pivot (0.2) (0.5) 1.1 sort complete | A1 | |
---3.
$$\begin{array} { l l l l l l l l l l }
1.1 & 0.7 & 1.9 & 0.9 & 2.1 & 0.2 & 2.3 & 0.4 & 0.5 & 1.7
\end{array}$$
\begin{enumerate}[label=(\alph*)]
\item Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 3
The list is to be sorted into descending order.
\item \begin{enumerate}[label=(\roman*)]
\item Starting at the left-hand end of the list, perform one pass through the list using a bubble sort. Write down the list that results at the end of your first pass.
\item Write down the number of comparisons and the number of swaps performed during your first pass.
After a second pass using this bubble sort, the updated list is
$$\begin{array} { l l l l l l l l l l }
1.9 & 1.1 & 2.1 & 0.9 & 2.3 & 0.7 & 0.5 & 1.7 & 0.4 & 0.2
\end{array}$$
\end{enumerate}\item Use a quick sort on this updated list to obtain the fully sorted list. You must make your pivots clear.
\item Apply the first-fit decreasing bin packing algorithm to your fully sorted list to pack the numbers into bins of size 3
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2015 Q3 [14]}}