| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2018 |
| Session | January |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Bubble Sort Execution |
| Difficulty | Easy -1.3 This question tests routine application of standard algorithms (bubble sort, quick sort, bin packing) with no problem-solving required. Students simply execute memorized procedures step-by-step. The bubble sort continuation is particularly mechanical—just following the algorithm from a given state. While multi-part, each component is a textbook exercise requiring only recall and careful execution. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin7.03m Packing extensions: 2D/3D packing and knapsack problems |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Bin 1: \(\underline{30}\ 11\ 21\ \boxed{16}\ \boxed{4}\) | M1 | First five items placed correctly and at least seven values placed in bins |
| Bin 2: \(\underline{53}\ \boxed{39}\) | A1 | First eight items placed correctly (underlined and boxed values) |
| Bin 3: \(\underline{50}\ 43\) | A1 | CSO (no additional/repeated values) |
| Bin 4: 60 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(11\ 21\ 16\ 4\ 30\ 39\ 43\ 50\ 53\ 60\) | B1 | CAO for fourth pass |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Comparisons: 6; Swaps: 2 | B1 B1 | CAO for comparisons (6); CAO for swaps (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Quick sort applied with pivot chosen from middle left or right | M1 | Pivot chosen from middle (choosing first/last item as pivot is M0) |
| First pass correct, next two pivots correctly chosen for second pass | A1 | |
| Second and third passes correct (follow through) | A1ft | |
| Sorted list: \(4\ 11\ 16\ 21\ 30\ 39\ 43\ 50\ 53\ 60\) | A1 | CSO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| First fit decreasing applied to sorted list in descending order | M1 | Must use 'sorted' list in descending order; first four items correctly placed and at least seven values in bins |
| Bin 1: \(\underline{60}\ \boxed{39}\); Bin 2: \(\underline{53}\ \boxed{43}\ 4\); Bin 3: \(\underline{50}\ \boxed{30}\ \boxed{16}\); Bin 4: \(\boxed{21}\ 11\) | A1 | First eight items placed correctly |
| CSO | A1 | No additional/repeated values |
# Question 6:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Bin 1: $\underline{30}\ 11\ 21\ \boxed{16}\ \boxed{4}$ | M1 | First five items placed correctly and at least seven values placed in bins |
| Bin 2: $\underline{53}\ \boxed{39}$ | A1 | First eight items placed correctly (underlined and boxed values) |
| Bin 3: $\underline{50}\ 43$ | A1 | CSO (no additional/repeated values) |
| Bin 4: 60 | | |
## Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $11\ 21\ 16\ 4\ 30\ 39\ 43\ 50\ 53\ 60$ | B1 | CAO for fourth pass |
## Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Comparisons: 6; Swaps: 2 | B1 B1 | CAO for comparisons (6); CAO for swaps (2) |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Quick sort applied with pivot chosen from middle left or right | M1 | Pivot chosen from middle (choosing first/last item as pivot is M0) |
| First pass correct, next two pivots correctly chosen for second pass | A1 | |
| Second and third passes correct (follow through) | A1ft | |
| Sorted list: $4\ 11\ 16\ 21\ 30\ 39\ 43\ 50\ 53\ 60$ | A1 | CSO |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| First fit decreasing applied to sorted list in descending order | M1 | Must use 'sorted' list in descending order; first four items correctly placed and at least seven values in bins |
| Bin 1: $\underline{60}\ \boxed{39}$; Bin 2: $\underline{53}\ \boxed{43}\ 4$; Bin 3: $\underline{50}\ \boxed{30}\ \boxed{16}$; Bin 4: $\boxed{21}\ 11$ | A1 | First eight items placed correctly |
| CSO | A1 | No additional/repeated values |6.
$$\begin{array} { l l l l l l l l l l }
30 & 11 & 21 & 53 & 50 & 39 & 16 & 4 & 60 & 43
\end{array}$$
The numbers in the list above represent the lengths, in cm, of some pieces of electrical wire. The wire is sold in one metre lengths.
\begin{enumerate}[label=(\alph*)]
\item Use the first-fit bin packing algorithm to determine how these pieces could be cut from one metre lengths. You should ignore wastage due to cutting.
The list of numbers above is to be sorted into ascending order.\\
Starting at the left-hand end of the list, after three passes of the bubble sort, the list is
$$\begin{array} { l l l l l l l l l l }
11 & 21 & 30 & 16 & 4 & 39 & 43 & 50 & 53 & 60
\end{array}$$
\item \begin{enumerate}[label=(\roman*)]
\item Write down the list that results at the end of the fourth pass.
\item Write down the number of comparisons and swaps performed during the fourth pass.
The original list of numbers is now to be sorted into descending order.
\end{enumerate}\item Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
\item Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from one metre lengths. You should ignore wastage due to cutting.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2018 Q6 [13]}}