| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2019 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Quick Sort Execution |
| Difficulty | Moderate -0.8 This is a multi-part question testing basic understanding of sorting algorithms rather than complex execution or analysis. Parts (a), (c), and (e) require simple recall of algorithm properties. Part (b) is straightforward application of O(n log n) complexity. Part (d) requires mechanical execution of quick sort on just 5 numbers. Only part (f) requires modest problem-solving to identify worst cases and count comparisons, but with n=5 this remains routine. Overall, this tests foundational knowledge with minimal computational or analytical challenge. |
| Spec | 7.03a Algorithm definition: input, output, deterministic, finite7.03g Order notation: O(n^k) for k = 0,1,2,3,47.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (a) | To ensure that the algorithm is finite |
| Or reference to using a stopping condition | B1 | 1.1 |
| Answer | Marks |
|---|---|
| refer to using a ‘stopping condition’ | Not ‘ because it is finite’ |
| Answer | Marks | Guidance |
|---|---|---|
| (b) | 20 seconds | B1 |
| Answer | Marks |
|---|---|
| (c) | Practical problems are usually large and cannot |
| be solved efficiently by ad hoc methods | B1 |
| B1 | 1.1 |
| 2.4 | 5000 |
| Answer | Marks |
|---|---|
| May take a long time otherwise | A computer would need |
| Answer | Marks |
|---|---|
| (d) | 41 17 8 33 29 |
| Answer | Marks |
|---|---|
| 8 17 29 33 41 | M1 |
| Answer | Marks |
|---|---|
| A1 | 1.1 |
| Answer | Marks |
|---|---|
| 1.1 | Pivot on first value |
| Answer | Marks |
|---|---|
| 33 and 29 | Any notation used |
| Answer | Marks | Guidance |
|---|---|---|
| (e) | Average case for bubble (or shuttle) sort is O(n2) | |
| O(n log n) ⊂ O(n2) | B1 | 1.2 |
| (f) | Worst case Comparisons |
| Answer | Marks |
|---|---|
| Both use 4 + 3 + 2 + 1 (= 10) comparisons | M1 |
| Answer | Marks |
|---|---|
| A1 | 1.1 |
| Answer | Marks |
|---|---|
| 1.1 | Worst case for quick sort (pivot 1st) |
| Answer | Marks |
|---|---|
| 10 or 4 + 3 + 2 + 1 seen, dep M1 M1 | Increasing or decreasing |
| Answer | Marks | Guidance |
|---|---|---|
| Worst case | Comparisons | |
| Quick sort | 8 17 29 33 41 | 10 |
| Bubble sort | 41 33 29 17 8 | 10 |
Question 4:
4 | (a) | To ensure that the algorithm is finite
Or reference to using a stopping condition | B1 | 1.1 | So it does not loop indefinitely
Not ‘count iterations’ unless also
refer to using a ‘stopping condition’ | Not ‘ because it is finite’
Not measuring efficiency
(b) | 20 seconds | B1 | 1.1 | 0.2 ×
2
(c) | Practical problems are usually large and cannot
be solved efficiently by ad hoc methods | B1
B1 | 1.1
2.4 | 5000
Large problems
�500�
Algorithms are more efficient
May take a long time otherwise | A computer would need
precise instructions
(d) | 41 17 8 33 29
17 8 33 29 41
8 17 33 29 41
8 17 29 33 41
8 17 29 33 41 | M1
A1
A1
A1 | 1.1
1.1
1.1
1.1 | Pivot on first value
First iteration correct
Second iteration correct with 17, 41
indicated in some way as being fixed
At least one more iteration to switch
33 and 29 | Any notation used
consistently
(e) | Average case for bubble (or shuttle) sort is O(n2)
O(n log n) ⊂ O(n2) | B1 | 1.2 | O(n log n) ⊂ O(n2) or in words
(f) | Worst case Comparisons
Quick sort 8 17 29 33 41 10
Bubble sort 41 33 29 17 8 10
Both use 4 + 3 + 2 + 1 (= 10) comparisons | M1
M1
A1 | 1.1
1.1
1.1 | Worst case for quick sort (pivot 1st)
Worst case for bubble sort
10 or 4 + 3 + 2 + 1 seen, dep M1 M1 | Increasing or decreasing
order or any other worst case
Decreasing order
Allow any calculation that
gives the answer 10
[12]
Worst case | Comparisons
Quick sort | 8 17 29 33 41 | 10
Bubble sort | 41 33 29 17 8 | 104 An algorithm must have an input, an output, be deterministic and finite.
\begin{enumerate}[label=(\alph*)]
\item Why is a counter sometimes used in an algorithm?
A computer takes 0.2 seconds to sort a list of 500 numbers.
\item How long would you expect the computer to take to sort a list of 5000 numbers?
Simon says that he can sort a list of numbers 'just by looking at them'.
\item Explain to Simon why sorting algorithms are needed.
\item Demonstrate how quick sort works by using it to sort the following list into increasing order. You should indicate the pivots used and which values are already known to be in their correct position.\\
$\begin{array} { l l l l l } 41 & 17 & 8 & 33 & 29 \end{array}$
For an average case the efficiency of quick sort is O (nlogn), where n is the number of items in the list.
\item Explain why quick sort is typically quicker than bubble sort and shuttle sort.
When the number of comparisons made is used as a measure of the efficiency, the worst case for quick sort is no more efficient than the worst case for bubble sort.
An arrangement of the five numbers from part (d) makes up a new list that is to be sorted using the bubble sort or the quick sort.
\item Without writing out all the passes, determine
\begin{itemize}
\item the worst case list
\item the total number of comparisons for the worst case list\\
for each of the algorithms in turn.
\end{itemize}
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2019 Q4 [12]}}