| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Counting Comparisons and Swaps |
| Difficulty | Easy -1.2 This is a straightforward algorithmic trace question requiring mechanical application of bubble sort with basic counting, followed by simple complexity calculations. Part (i) is routine execution, part (ii) requires recognizing reverse order maximizes swaps (standard textbook knowledge), and part (iii) is a direct quadratic scaling calculation (100^2 = 10000 times longer). No problem-solving insight or novel reasoning required—purely procedural application of D1 content. |
| Spec | 7.03d Order of algorithm: dominant term and scaling run-times7.03j Sorting: bubble sort and shuttle sort |
Question 2:
2
Answer all the questions in the printed answer book provided.
Section A (24 marks)
1 Each of the following symbols consists of boundaries enclosing regions.
00 11 22 33 44 55 66 77 88 99
The symbol representing zero has three regions, the outside, that between the two boundaries and
the inside.
To classify the symbols a graph is produced for each one. The graph has a vertex for each region,
with arcs connecting regions which share a boundary. Thus the graph for
00
is .
44
(i) Produce the graph for the symbol . [1]
(ii) Give two symbols each having the graph . [2]
88
(iii) Produce the graph for the symbol . [2]
8888
(iv) Produce a single graph for the composite symbol . [2]
(v) Give the name of a connected graph with n nodes and n (cid:1) 1 arcs. [1]The following algorithm is a version of bubble sort.
Step 1 \quad Store the values to be sorted in locations L(1), L(2), $\ldots$ , L(n) and set i to be the number, n, of values to be sorted.
Step 2 \quad Set j = 1.
Step 3 \quad Compare the values in locations L(j) and L(j+1) and swap them if that in L(j) is larger than that in L(j+1).
Step 4 \quad Add 1 to j.
Step 5 \quad If j is less than i then go to step 3.
Step 5 \quad Write out the current list, L(1), L(2), $\ldots$ , L(n).
Step 6 \quad Subtract 1 from i.
Step 7 \quad If i is larger than 1 then go to step 2.
Step 8 \quad Stop.
\begin{enumerate}[label=(\roman*)]
\item Apply this algorithm to sort the following list.
109 \quad 32 \quad 3 \quad 523 \quad 58.
Count the number of comparisons and the number of swaps which you make in applying the algorithm. [4]
\item Put the five values into the order which maximises the number of swaps made in applying the algorithm, and give that number. [2]
\item Bubble sort has quadratic complexity. Using bubble sort it takes a computer 1.5 seconds to sort a list of 1000 values. Approximately how long would it take to sort a list of 100 000 values? (Give your answer in hours and minutes.) [2]
\end{enumerate}
\hfill \mbox{\textit{OCR MEI D1 2007 Q2 [8]}}