Easy -1.2 This is a straightforward procedural question requiring mechanical application of the quick sort algorithm with no problem-solving or insight needed. Students simply follow the standard algorithm steps, choosing pivots and partitioning—pure recall and execution of a learned procedure, making it easier than average.
1.
$$\begin{array} { l l l l l l l l l l l }
67 & 59 & 46 & 71 & 40 & 48 & 53 & 63 & 45 & 54 & 56
\end{array}$$
The list of eleven numbers shown above is to be sorted into descending order.
Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify the pivots clearly.
Quick Sort using middle right or middle left pivot selection. After first pass: (values > pivot), pivot, (values < pivot). If only one pivot per iteration, M1 only. Original list of 10/11/12 numbers must remain 10/11/12 numbers after first pass.
Third and fourth passes correct (follow through from second pass and consistent pivots). After second pass list must contain 10/11/12 numbers (allow one additional/missing number).
SC: If list sorted into ascending order, award maximum M1A1A0A0 (2 marks), even if re-ordered after sort is complete.
Total: (4 marks)
## Question 1: Quick Sort
| Answer/Working | Marks | Guidance Notes |
|---|---|---|
| **Middle right pivot method:** | | |
| 67 59 46 71 40 **48** 53 63 45 54 56 → pivot: 48 | M1 | Quick Sort using middle right or middle left pivot selection. After first pass: (values > pivot), pivot, (values < pivot). If only one pivot per iteration, M1 only. Original list of 10/11/12 numbers must remain 10/11/12 numbers after first pass. |
| 67 59 71 **53** 63 54 56 <u>48</u> 46 **40** 45 → pivots: 53, 40 | A1 | First two passes correct (pivots for third pass need not be chosen) |
| 67 59 71 **63** 54 56 <u>53</u> <u>48</u> 46 **45** <u>40</u> → pivots: 63, 45 | A1ft | Third and fourth passes correct (follow through from second pass and consistent pivots). After second pass list must contain 10/11/12 numbers (allow one additional/missing number). |
| <u>71</u> 67 <u>63</u> 59 **56** 54 <u>53</u> <u>48</u> 46 <u>45</u> <u>40</u> → pivots: (67), 56 | A1 | cso – must include a fifth pass if choosing middle right pivots. |
| <u>71</u> 67 <u>63</u> 59 <u>56</u> 54 <u>53</u> <u>48</u> 46 <u>45</u> <u>40</u> | | |
**SC:** If list sorted into ascending order, award maximum M1A1A0A0 (2 marks), even if re-ordered after sort is complete.
**Total: (4 marks)**
1.
$$\begin{array} { l l l l l l l l l l l }
67 & 59 & 46 & 71 & 40 & 48 & 53 & 63 & 45 & 54 & 56
\end{array}$$
The list of eleven numbers shown above is to be sorted into descending order.\\
Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify the pivots clearly.\\
\hfill \mbox{\textit{Edexcel FD1 AS 2023 Q1 [4]}}