| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Bubble Sort Execution |
| Difficulty | Easy -1.3 This is a straightforward D1 question testing standard algorithm execution with no problem-solving required. Part (a) requires mechanical application of one bubble sort pass, part (b) is routine quick sort execution, and part (c) uses the basic lower bound formula (sum/bin size). All are textbook procedures with no conceptual challenges or novel insights needed. |
| 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 |
| Either: 11 10 14 8 13 6 4 15 7 17 Or: 4 11 17 10 14 8 13 6 7 15 | M1 A1 (2) | M1: Bubble sort, end number in place correctly. A1: CAO – isw after one complete pass. SC: If list sorted into ascending order, must be fully correct: 17 11 14 10 13 8 6 15 7 4 or 17 11 15 10 14 8 13 6 4 7 scores M1A0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Pass 1: pivot 13; Pass 2: pivots 14, 6; Pass 3: pivots 15, 8 (4); Pass 4: pivots (17), 10, (7); sort complete | M1, 1A1, 2A1ft, 3A1 (4) | M1: Quick sort – pivots selected, first pass gives \( |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(\dfrac{105}{26} \approx 4.0385\) so 5 bins needed | M1 A1 (2) | M1: Attempt to find lower bound \((105 \pm 17)/26\), or answer correct to 3 sf (accept 4.03 or 4.04). Must be a numerical argument. A1: CSO including 5 (5 with no working scores M0). |
# Question 1:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Either: 11 10 14 8 13 6 4 15 7 17 Or: 4 11 17 10 14 8 13 6 7 15 | M1 A1 **(2)** | M1: Bubble sort, end number in place correctly. A1: CAO – isw after one complete pass. SC: If list sorted into ascending order, must be fully correct: 17 11 14 10 13 8 6 15 7 4 **or** 17 11 15 10 14 8 13 6 4 7 scores M1A0 |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Pass 1: pivot 13; Pass 2: pivots 14, 6; Pass 3: pivots 15, 8 (4); Pass 4: pivots (17), 10, (7); sort complete | M1, 1A1, 2A1ft, 3A1 **(4)** | M1: Quick sort – pivots selected, first pass gives $<p$, $p$, $>p$. **If only choosing 1 pivot per iteration M1 only. Bubble sort here is M0.** 1A1: First pass correct, pivots chosen consistently for second pass. 2A1ft: Second and third passes correct (ft from first pass). 3A1: CSO all correct including choice of pivots for fourth pass, then **either** a 'stop' statement **or** final re-listing **or** using each item as a pivot. |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $\dfrac{105}{26} \approx 4.0385$ so 5 bins needed | M1 A1 **(2)** | M1: Attempt to find lower bound $(105 \pm 17)/26$, **or** answer correct to 3 sf (accept 4.03 or 4.04). Must be a numerical argument. A1: CSO including 5 (5 with no working scores M0). |
**Total: 8 marks**1.
11\\
17\\
10\\
14\\
8\\
13\\
6\\
4\\
15\\
7
\begin{enumerate}[label=(\alph*)]
\item Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order.
The original list is now to be sorted into descending order.
\item Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear.
The numbers are to be packed into bins of size 26
\item Calculate a lower bound for the minimum number of bins required. You must show your working.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2014 Q1 [8]}}