AQA D1 2007 January — Question 4 8 marks

Exam BoardAQA
ModuleD1 (Decision Mathematics 1)
Year2007
SessionJanuary
Marks8
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicSorting Algorithms
TypeCounting Comparisons and Swaps
DifficultyModerate -0.8 This is a straightforward D1 question requiring only direct observation of a worked example and recall of bubble sort formulas. Part (a) involves counting from given data, and part (b) uses standard formulas (max comparisons = n(n-1)/2, max swaps same for worst case). No problem-solving or algorithmic insight required.
Spec7.03j Sorting: bubble sort and shuttle sort
4
  1. A student is using a bubble sort to rearrange seven numbers into ascending order.
    Her correct solution is as follows:
    Initial list18171326101424
    After 1st pass17131810142426
    After 2nd pass13171014182426
    After 3rd pass13101417182426
    After 4th pass10131417182426
    After 5th pass10131417182426
    Write down the number of comparisons and swaps on each of the five passes.
  2. Find the maximum number of comparisons and the maximum number of swaps that might be needed in a bubble sort to rearrange seven numbers into ascending order.
4(a)
AnswerMarks Guidance
Comparisons: 6, 5, 4, 3, 2 with Swaps: 5, 3, 2, 1, 0B1B1, B1B1, B1, B1 Other 3 comparisons; Other 3 swaps. Ignore 6th pass (6 marks total)
4(b)
AnswerMarks Guidance
\(21\); \(21\)B1, B1 (2 marks total) 
**4(a)**
| Comparisons: 6, 5, 4, 3, 2 with Swaps: 5, 3, 2, 1, 0 | B1B1, B1B1, B1, B1 | Other 3 comparisons; Other 3 swaps. Ignore 6th pass (6 marks total) |

**4(b)**
| $21$; $21$ | B1, B1 | (2 marks total) |
4
\begin{enumerate}[label=(\alph*)]
\item A student is using a bubble sort to rearrange seven numbers into ascending order.\\
Her correct solution is as follows:

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
Initial list & 18 & 17 & 13 & 26 & 10 & 14 & 24 \\
\hline
After 1st pass & 17 & 13 & 18 & 10 & 14 & 24 & 26 \\
\hline
After 2nd pass & 13 & 17 & 10 & 14 & 18 & 24 & 26 \\
\hline
After 3rd pass & 13 & 10 & 14 & 17 & 18 & 24 & 26 \\
\hline
After 4th pass & 10 & 13 & 14 & 17 & 18 & 24 & 26 \\
\hline
After 5th pass & 10 & 13 & 14 & 17 & 18 & 24 & 26 \\
\hline
\end{tabular}
\end{center}

Write down the number of comparisons and swaps on each of the five passes.
\item Find the maximum number of comparisons and the maximum number of swaps that might be needed in a bubble sort to rearrange seven numbers into ascending order.
\end{enumerate}

\hfill \mbox{\textit{AQA D1 2007 Q4 [8]}}
This paper (8 questions)
View full paper
Q1 10 Q2 6 Q3 8 Q4 8 Q5 8 Q6 13 Q7 14 Q8 8