OCR A-Level Computer Science Algorithms and programming (02), June 2025: Question 1

22 marks · Medium difficulty · Algorithm / Pseudo-code

Explain the operation of bubble sort and insertion sort, and analyze pseudocode implementing a recursive quick sort algorithm.

Practise this question

Question

Question text

1 Data in a computer program needs to be sorted.

(a)

(i) Describe the steps a bubble sort will take to sort items into ascending order.

… [5]

(ii) Darcie and Felix have both written a program that will perform a bubble sort to put these numbers

into ascending order.

21 3 4 5 6 7

Darcie’s version will complete six passes. However, Felix’s version will only need to complete

two passes.

Explain how Felix may have made his version more efficient than Darcie’s version.

… [2]

(b) A second type of sorting algorithm is an insertion sort.

Describe how an insertion sort can be used to put the following data into ascending order.

20 8 15 36

… [5]

The following quick sort algorithm is made up of two functions called partition() and

quickSort(). The algorithm will sort an integer array into ascending numerical order.

01 function partition(array, low, high)

02 pivot = array[high]

03 index = low - 1

04 for count = low to high-1

05 if array[count] < pivot then

06 index = index + 1

07 temp = array[index]

08 array[index] = array[count]

09 array[count] = temp

10 endif

11 next count

12 temp = array[index + 1]

13 array[index + 1] = array[high]

14 array[high] = temp

15 return index + 1

16 endfunction

18 function quickSort(array, low, high)

19 if low < high then

20 partitionIndex = partition(array, low, high)

21 quickSort(array, low, partitionIndex - 1)

22 quickSort(array, partitionIndex + 1, high)

23 endif

24 endfunction

(i) Identify which of the two functions is recursive and give all of the line numbers where recursive

calls are made.

Recursive function name …

Recursive call line numbers …

[2]

(ii) Identify the type of iteration used in the function partition().

… [1]

(iii) Describe the role of the function partition() in the quick sort algorithm.

… [3]

(iv) The algorithm needs to be changed to sort the integer array into descending numerical order.

Identify the line number that needs to be changed and write the amended line of code.

Line number …

Amended line of code …

[2]

(v) The quick sort is an example of a divide-and-conquer algorithm.

Describe what divide-and-conquer means.

… [2]

Mark scheme

Show the mark scheme

Question Answer Mark Guidance

1 (a) (i) 1 mark each to max 5 5 BP2 comparison can be implicit

e.g. if first item is greater than

• Set a flag/Boolean value the second item

• Compare the first pair / adjacent two items BP3 must explicitly state ‘no

• If the items are in the correct order no swap is needed swap’ if two items are in the

• If the items are in the wrong order, then swap them around… correct order.

• …using a temporary variable

• …change the flag/Boolean value BP8 is dependent on BP7, BP8

cannot be awarded unless it is

• Repeat comparison of pairs of items until end of pass… clear multiple passes are

performed.

• ...until all items sorted/max number of passes reached

BP8 swap flag solution will be

until no swaps occur in a pass

as equivalent to all sorted

1 (a) (ii) 1 mark each to max 2 2 Responses must work for two

passes, which means a swap

• May have set a flag/Boolean value… flag/equivalent must be

• ….that can be used to indicate if a swap has been made referenced.

• Checks if there are no swaps made (in the last pass)

• … and stops the loop from continuing

1 (b) 1 mark each to max 5 5 Allow annotated diagrams

6 Sorted Unsorted

• Insertion sort uses a ‘sorted’ and ‘unsorted’ list

• Initially the unsorted list is [20,8,15,36]

• In the first pass, 20 is taken from the unsorted list and placed into the | 20 8 15 36

sorted list // sorted becomes [20] and unsorted becomes [8,15,36] 20 | | 8 15 36

• In the next pass the next item 8, is inserted into its correct position in 8 20 | | 15 36

8 15 20 | | 36

the sorted list // sorted becomes [8, 20] and unsorted becomes [15,36]

8 15 20 36 |

• In the next pass the next item 15, is inserted into its correct position in

the sorted list // sorted becomes [8, 15, 20] and unsorted becomes

[36] MP1 may be shown implicitly by

lists being separated.

• In the final pass 36 in inserted into the correct position // sorted

becomes [8, 15, 20, 36]

Responses must apply to the

data set given. Do not credit

generic responses.

Max 4 if descending order.

1 (c) (i) 1 mark for name quickSort // quickSort() 2 Ignore case

1 mark for both lines 21 and 22 Allow sight of quicksort

1 (c) (ii) Count controlled // for loop 1 Allow ‘definite’

1 (c) (iii) 1 mark each to max 3 3 Allow the reverse for BP3 and

BP4 i.e. items greater are

• Select a pivot placed to the left and items

• Compare each value to the pivot smaller are placed to the right

• values less than the pivot are placed to the left of it (for descending sort)

• values greater than the pivot are placed to the right of it

1 (c) (iv) 1 mark for line number 05 // 5 2 Allow >= instead of >

1 mark for the amended line: if array[count] > pivot then Full line of code must be given

1 (c) (v) 1 mark each to max 2 2 Allow responses that apply to

the sorting of the lists/data in

• Breaks down the problem into smaller sub problems quicksort.

• Finds a solution to each smaller sub problem separately

• Combines the solutions from the sub problems together

• Returns the combined solutions

How to answer it

Standard Sorting Algorithms & Divide-and-Conquer

📋 What this question tests

This multi-part question tests your fundamental understanding and algorithmic tracing of three core syllabus sorting algorithms alongside core computational methodology:

Bubble Sort: Step-by-step mechanism, adjacent element comparisons, swapping with a temporary variable, and early termination flags.
Insertion Sort: Step-by-step tracing with explicit division between "sorted" and "unsorted" sublists on given data.
Quick Sort Analysis: Code comprehension, identifying recursion lines, loop categorization, pivot-partitioning logic, modifying relational conditions for descending order, and the general principles of divide-and-conquer.

Part (a) Bubble Sort Mechanics & Optimization

(a)(i) Describing Bubble Sort Steps [5 Marks] & (a)(ii) Early Exit Optimization [2 Marks]

✅ Ideal Model Answers

(a)(i) Steps for Ascending Bubble Sort:

Initialize a Boolean flag (e.g. swapped = False ).
Compare the first adjacent pair of elements.
If they are in the correct order, make no swap; if they are out of order, swap them using a temporary variable and set the flag to True .
Move to the next adjacent pair and repeat until reaching the end of the pass.
Repeat the entire pass until a pass completes with no swaps made (flag remains False ) or maximum passes are reached.

(a)(ii) Felix's Optimization:

Felix used a swap flag (Boolean variable) that tracks if any exchange takes place. On pass 2, no swaps occur because the array is already sorted, allowing the algorithm to detect this and terminate immediately.

🧠 Exam Technique & Mark Scheme Rules

Be Explicit About 'No Swap': The mark scheme strictly dictates that candidate responses must state that "no swap is needed" when items are already in order to gain that specific mark.
Temporary Variable: Always state that swapping items requires a temporary variable or placeholder.
Dependent Marks: Explaining that passes repeat is required before marks for termination condition (all sorted / flag unchanged) can be awarded.
Application in (a)(ii): You must explain why it takes 2 passes: pass 1 puts 1 and 2 in order; pass 2 checks all adjacent items, makes 0 swaps, and exits.

❌ Common Pitfalls in Bubble Sort Questions

Vague comparisons: Saying "compare all numbers" instead of explicitly stating "compare adjacent pairs / pairs of items".
Assuming fixed passes: Forgetting to mention how the algorithm knows when it has finished (early termination vs n - 1 passes).

Part (b) Tracing Insertion Sort

Detailed Trace on Array: [20, 8, 15, 36] [5 Marks]

✅ Step-by-Step Trace (Applying to the Data Set)

Initial State: The list is split into a sorted sublist and an unsorted sublist. Unsorted: [20, 8, 15, 36] .
Pass 1: First item 20 is placed into the sorted list.
Sorted: [20] | Unsorted: [8, 15, 36] .
Pass 2: Next item 8 is compared and inserted before 20 .
Sorted: [8, 20] | Unsorted: [15, 36] .
Pass 3: Next item 15 is compared and inserted between 8 and 20 .
Sorted: [8, 15, 20] | Unsorted: [36] .
Pass 4: Next item 36 is compared and placed at the end.
Sorted: [8, 15, 20, 36] | Unsorted: [] .

💡 Examiner Guidance & Marking Notes

Pass	Sorted Sublist	Unsorted Sublist
Start	[ ]	[20, 8, 15, 36]
1	[20]	[8, 15, 36]
2	[8, 20]	[15, 36]
3	[8, 15, 20]	[36]
4	[8, 15, 20, 36]	[ ]

Crucial Rule: Generic algorithm descriptions score 0 marks. You must explicitly apply every step to the numbers 20, 8, 15, and 36. An annotated trace table or pipeline diagram is fully accepted.

Part (c) Quick Sort Code Comprehension & Divide-and-Conquer

Inspecting the Provided Pseudocode & Algorithmic Properties

✅ Accurate Answers & Mark Allocation

(c)(i) Recursive Function & Lines [2 Marks]:
Name: quickSort (or quickSort() )
Lines: 21 and 22 (Both required for the 2nd mark).
(c)(ii) Iteration Type in partition() [1 Mark]:
Count-controlled loop (also accept: for loop or definite iteration).
(c)(iii) Role of partition() [3 Marks]:
Selects a pivot element, compares every element to the pivot, places values smaller than the pivot to its left, and places values larger than the pivot to its right.
(c)(iv) Amending to Descending Order [2 Marks]:
Line Number: 05 (or 5)
Amended Line: if array[count] > pivot then (or >= )
(c)(v) Meaning of Divide-and-Conquer [2 Marks]:
Breaks down a complex problem into smaller sub-problems, solves each sub-problem independently/recursively, and combines the sub-solutions into a complete solution.

🧠 Examiner Insights & Traps to Avoid

Forgetting the full line: In part (c)(iv), the question asks to "write the amended line of code". Writing just > scores 0 for that mark. You must supply: if array[count] > pivot then .
Both recursive lines: In part (c)(i), notice line 20 is a non-recursive function call to partition() . The recursive self-calls occur on both line 21 (left partition) and line 22 (right partition).
Precise Iteration Terminology: Iteration governed by a fixed boundary like for count = low to high-1 is definite / count-controlled. Condition-based iteration ( while / repeat until ) is indefinite / condition-controlled.

📐 Summary Checklist: Divide-and-Conquer Triad

Whenever asked to define or describe Divide-and-Conquer in OCR A-Level Computer Science, ensure your answer addresses all three stages:

Divide: Splitting the data/problem into smaller instances of the same problem (e.g., partitioning around the pivot).
Conquer: Solving the sub-problems recursively (handling base cases when array size ≤ 1).
Combine: Recombining sub-solutions to yield the fully sorted array.

Topics

2.2 Problem solving and programming · 2.3 Algorithms · 2.2.1 Programming techniques · 2.2.2 Computational methods · 2.3.1 Algorithms

Question and mark scheme from the OCR A-Level Computer Science examination, Algorithms and programming (02), June 2025. QuestionVault is an independent revision resource; questions remain the copyright of the awarding body.