OCR Further Discrete 2023 June — Question 5 12 marks

Exam BoardOCR
ModuleFurther Discrete (Further Discrete)
Year2023
SessionJune
Marks12
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicSorting Algorithms
TypeQuick Sort Execution
DifficultyModerate -0.5 This is a straightforward application of the quick sort algorithm with standard bookwork questions. Part (a) requires mechanical execution of the algorithm, parts (b) and (d) test basic understanding of best/worst cases, and part (c) is a routine O(n²) calculation. While it requires careful work across multiple parts, it demands no novel insight beyond applying learned procedures and formulas.
Spec7.03g Order notation: O(n^k) for k = 0,1,2,3,47.03k Sorting: quick sort
5 A list of 8 values is given below.
324814203018
The list is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
  1. Carry out the first two passes of the sort. A different list of 8 values is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
    1. State the maximum number of passes that could be required.
    2. Find the minimum number of passes that could be required. The run-time for quick sort could be measured by counting the number of comparisons used. In the worst case, the run time for quick sort is \(\mathrm { O } \left( n ^ { 2 } \right)\). A computer takes at most 0.03 seconds to sort a list of 100 values into increasing order using quick sort.
  3. Calculate an estimate for the time taken, in the worst case, to sort a list of 500 values using quick sort. A list of \(n\) values (where \(n > 10\) ) is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
  4. Explain why, in the best case, \(n - 3\) comparisons are used in the second pass.
Question 5:
AnswerMarks Guidance
5(a) First pass 1 3 24 8 4 20 30 18
Second pass 1 3 8 4 20 18 24 30M1
A1
M1
A1
AnswerMarks
[4]1.1
1.1
1.1
AnswerMarks
1.1List starts 1 3 24
cao
List ends 24 30
cao
AnswerMarks Guidance
5(b) (i)
[1]1.1 cao
5(b) (ii)
3M1
A1
AnswerMarks
[2]2.1
1.1Allow for 3 or 4 as answer
e.g. x x x X x x x x → x X x X x X x x → x X x X x X x X
cao
AnswerMarks Guidance
5(c) 0.03  52
= 0.75 (seconds)M1
A1
AnswerMarks
[2]1.2
1.1A valid calculation seen or implied
2
500 0.03 𝑡
e.g. (310-6) 5002, 0.03×( ) , =
100 1002 5002
0.75, 3 or 7.510-1
4
AnswerMarks Guidance
5(d) In the best case no sublist has length 0
After one pass there is 1 fixed value and
two sublists with a total of n – 1 values to
be sorted
Each of the other values are compared with
a pivot, apart from the pivots
There are 2 pivots in the second pass
AnswerMarks
Hence n – 3B1
M1
AnswerMarks
A12.2a
2.2a
AnswerMarks
2.2aNo sublist of length 0, allow for ‘2 sublists after first pass’
n – 1 values to be sorted after first pass (or 1 value is fixed)
May be implied from n – 1 – 2 seen (but note that n – 3 is given)
2 pivots used in second pass (in best case)
Must be explicitly identified as pivots
n – 1 – 2 is not enough here
Reasoning leading to n – 3 values to be compared with pivots
Note: if candidate claims that the best case is when n is odd (or 1
less than a power of 2) and then proceeds with this approach they
can get B0, M1, A1 max
AnswerMarks
Alternative method 1Note: n is a given value so it may be odd or even
After one pass: for odd n, in the best case,
the sublists both have length (n – 1)/2
Each value in sublists compared with pivot
 2[(n – 1)/2 – 1] = n – 3 comparisons in
AnswerMarks Guidance
second passAfter one pass: for odd n, in the best case, B1
the sublists both have length (n – 1)/2
Each value in sublists compared with pivot
 2[(n – 1)/2 – 1] = n – 3 comparisons in
After one pass: for even n, in the best case
AnswerMarks Guidance
the sublists have length (n/2) and (n/2) – 1M1 Even n  sublist of length (n/2) or (n/2) – 1 (either)
Each value in sublists compared with pivot
AnswerMarks Guidance
 [(n/2) – 1] + [(n/2) – 2] = n – 3A1 Both (n/2) and (n/2) – 1
Reasoning leading to n – 3 values to be compared with pivotsBoth (n/2) and (n/2) – 1
Alternative method 2
AnswerMarks Guidance
Result(s) deduced from specific casesB1 At least two numerical cases when n is odd, leading to n – 3
[max 2 marks]SC B1 At least two numerical cases when n is even, leading to n – 3
[3]
Question 5:
5 | (a) | First pass 1 3 24 8 4 20 30 18
Second pass 1 3 8 4 20 18 24 30 | M1
A1
M1
A1
[4] | 1.1
1.1
1.1
1.1 | List starts 1 3 24
cao
List ends 24 30
cao
5 | (b) | (i) | 7 | B1
[1] | 1.1 | cao
5 | (b) | (ii) | Sublist lengths roughly half each time
3 | M1
A1
[2] | 2.1
1.1 | Allow for 3 or 4 as answer
e.g. x x x X x x x x → x X x X x X x x → x X x X x X x X
cao
5 | (c) | 0.03  52
= 0.75 (seconds) | M1
A1
[2] | 1.2
1.1 | A valid calculation seen or implied
2
500 0.03 𝑡
e.g. (310-6) 5002, 0.03×( ) , =
100 1002 5002
0.75, 3 or 7.510-1
4
5 | (d) | In the best case no sublist has length 0
After one pass there is 1 fixed value and
two sublists with a total of n – 1 values to
be sorted
Each of the other values are compared with
a pivot, apart from the pivots
There are 2 pivots in the second pass
Hence n – 3 | B1
M1
A1 | 2.2a
2.2a
2.2a | No sublist of length 0, allow for ‘2 sublists after first pass’
n – 1 values to be sorted after first pass (or 1 value is fixed)
May be implied from n – 1 – 2 seen (but note that n – 3 is given)
2 pivots used in second pass (in best case)
Must be explicitly identified as pivots
n – 1 – 2 is not enough here
Reasoning leading to n – 3 values to be compared with pivots
Note: if candidate claims that the best case is when n is odd (or 1
less than a power of 2) and then proceeds with this approach they
can get B0, M1, A1 max
Alternative method 1 | Note: n is a given value so it may be odd or even
After one pass: for odd n, in the best case,
the sublists both have length (n – 1)/2
Each value in sublists compared with pivot
 2[(n – 1)/2 – 1] = n – 3 comparisons in
second pass | After one pass: for odd n, in the best case, | B1 | B1 | Odd n  two sublists of length (n – 1)/2 | Odd n  two sublists of length (n – 1)/2
the sublists both have length (n – 1)/2
Each value in sublists compared with pivot
 2[(n – 1)/2 – 1] = n – 3 comparisons in
After one pass: for even n, in the best case
the sublists have length (n/2) and (n/2) – 1 | M1 | Even n  sublist of length (n/2) or (n/2) – 1 (either)
Each value in sublists compared with pivot
 [(n/2) – 1] + [(n/2) – 2] = n – 3 | A1 | Both (n/2) and (n/2) – 1
Reasoning leading to n – 3 values to be compared with pivots | Both (n/2) and (n/2) – 1
Alternative method 2
Result(s) deduced from specific cases | B1 | At least two numerical cases when n is odd, leading to n – 3
[max 2 marks] | SC B1 | At least two numerical cases when n is even, leading to n – 3
[3]
5 A list of 8 values is given below.

\begin{center}
\begin{tabular}{ l l l l l l l l }
3 & 24 & 8 & 1 & 4 & 20 & 30 & 18 \\
\end{tabular}
\end{center}

The list is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
\begin{enumerate}[label=(\alph*)]
\item Carry out the first two passes of the sort.

A different list of 8 values is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
\item \begin{enumerate}[label=(\roman*)]
\item State the maximum number of passes that could be required.
\item Find the minimum number of passes that could be required.

The run-time for quick sort could be measured by counting the number of comparisons used. In the worst case, the run time for quick sort is $\mathrm { O } \left( n ^ { 2 } \right)$.

A computer takes at most 0.03 seconds to sort a list of 100 values into increasing order using quick sort.
\end{enumerate}\item Calculate an estimate for the time taken, in the worst case, to sort a list of 500 values using quick sort.

A list of $n$ values (where $n > 10$ ) is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
\item Explain why, in the best case, $n - 3$ comparisons are used in the second pass.
\end{enumerate}

\hfill \mbox{\textit{OCR Further Discrete 2023 Q5 [12]}}
This paper (7 questions)
View full paper
Q1 7 Q2 8 Q3 12 Q4 10 Q5 12 Q6 14 Q7 12