Quicksort partitions a list around a pivot value: elements smaller than the pivot are moved before it, and elements larger are moved after it.
The list [10, 4, 15, 2, 8, 12] is partitioned using the lower of the two middle elements (index 2), 15, as the pivot. The elements in each sublist keep their original relative order.
State the two sublists formed either side of the pivot after partitioning, and the pivot's final index (counting from 0).
Answer
Before pivot: [10,4,2,8,12]; pivot 15 at index 5; after pivot: [].
Mark scheme
| M1 | for identifying the middle element (index 2), value 15, as the pivot |
| M1 | for comparing each remaining element, 10, 4, 2, 8, 12, against the pivot value 15 |
| A1 | for recognising every one of these elements is smaller than 15 |
| A1 | for concluding no elements belong after the pivot, so the pivot moves to the last index, index 5 |
| B1 | for the sublist before the pivot containing all five remaining elements, 10, 4, 2, 8, 12, in their original relative order Award all 5 marks for the complete correct requested answer: Using the explicitly named pivot 15: before pivot [10,4,2,8,12]; after pivot []; final index 5. The list has two middle positions, so the wording should identify index 2 (the lower middle). Accept equivalent valid notation and explanations. Intermediate method evidence below is optional and may be inferred from a correct requested result; do not require unasked states or extra explanations. |