| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Describing Sorting Algorithm Steps |
| Difficulty | Easy -1.8 This is a purely procedural question testing recall and mechanical application of standard algorithms (bubble sort and bin packing). No problem-solving, proof, or mathematical insight required—students simply execute memorized steps and state basic facts about the algorithms. |
| 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 |
| Compare first value with second value, swap if second is larger; then compare new second with third, continue to end of list | M1 A1 | Must be clear first value compared with second, swapping if second is larger |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| The smallest value will be in the correct final position after the first pass | B1 | CAO (allow 1) — smallest value from list in (c) |
| Maximum number of passes is \(n - 1\) | B1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(1^{\text{st}}\) pass: 11, 9, 13, 5, 4, 7, 12, 8, 1 | M1 | Bubble sort, consistent direction, end number (1) in place |
| \(2^{\text{nd}}\) pass: 11, 13, 9, 5, 7, 12, 8, 4, 1 | A1 | First and second passes correct — end two numbers in place |
| \(3^{\text{rd}}\) pass: 13, 11, 9, 7, 12, 8, 5, 4, 1 | ||
| \(4^{\text{th}}\) pass: 13, 11, 9, 12, 8, 7, 5, 4, 1 | A1ft | Third and fourth passes correct following through from candidate's second pass |
| \(5^{\text{th}}\) pass: 13, 11, 12, 9, 8, 7, 5, 4, 1 | ||
| \(6^{\text{th}}\) pass: 13, 12, 11, 9, 8, 7, 5, 4, 1 | ||
| Sort complete | A1(cso) | CSO — including either 'sort complete' statement or final list rewritten/seventh pass |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Bin 1: 13, 8; Bin 2: 12, 9; Bin 3: 11, 7, 1; Bin 4: 5, 4 | M1 A1 | Bins 1 and 2 correct and 11 in Bin 3 (first 5 values correctly placed) — no follow through on incorrect list from (c); CSO |
# Question 2:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Compare first value with second value, swap if second is larger; then compare new second with third, continue to end of list | M1 A1 | Must be clear first value compared with second, swapping if second is larger |
## Part (b)(i) and (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| The smallest value will be in the correct final position after the first pass | B1 | CAO (allow 1) — smallest value from list in (c) |
| Maximum number of passes is $n - 1$ | B1 | CAO |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $1^{\text{st}}$ pass: 11, 9, 13, 5, 4, 7, 12, 8, **1** | M1 | Bubble sort, consistent direction, end number (1) in place |
| $2^{\text{nd}}$ pass: 11, 13, 9, 5, 7, 12, 8, **4**, **1** | A1 | First and second passes correct — end two numbers in place |
| $3^{\text{rd}}$ pass: 13, 11, 9, 7, 12, 8, **5**, **4**, **1** | | |
| $4^{\text{th}}$ pass: 13, 11, 9, 12, 8, **7**, **5**, **4**, **1** | A1ft | Third and fourth passes correct following through from candidate's second pass |
| $5^{\text{th}}$ pass: 13, 11, 12, 9, **8**, **7**, **5**, **4**, **1** | | |
| $6^{\text{th}}$ pass: 13, 12, 11, **9**, **8**, **7**, **5**, **4**, **1** | | |
| Sort complete | A1(cso) | CSO — including either 'sort complete' statement **or** final list rewritten/seventh pass |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Bin 1: 13, 8; Bin 2: 12, 9; Bin 3: 11, 7, 1; Bin 4: 5, 4 | M1 A1 | Bins 1 and 2 correct and 11 in Bin 3 (first 5 values correctly placed) — no follow through on incorrect list from (c); CSO |
---2. A list of $n$ numbers needs to be sorted into descending order starting at the left-hand end of the list.
\begin{enumerate}[label=(\alph*)]
\item Describe how to carry out the first pass of a bubble sort on the numbers in the list.
\item \begin{enumerate}[label=(\roman*)]
\item State which number in the list is guaranteed to be in the correct final position after the first pass.
\item Write down the maximum number of passes required to sort a list of $n$ numbers.
\end{enumerate}\item The numbers below are to be sorted into descending order. Use a bubble sort, starting at the left-hand end of the list, to obtain the sorted list. You need only give the state of the list after each pass.
$$\begin{array} { l l l l l l l l l }
11 & 9 & 4 & 13 & 5 & 1 & 7 & 12 & 8
\end{array}$$
\item Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 21
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2015 Q2 [10]}}