OCR GCSE Computer Science June 2023 Paper 2, Question 3: the insertion sort

OCR J277/02 June 2023, Question 3: the purpose of temp in an insertion sort, why its inner loop is condition-controlled, and how insertion sort and bubble sort differ and agree. Worked answers, with the sort to run step by step.

Past paper questionOCR J277/02June 2023 Paper 28 marksExplain

Question 3 of the OCR GCSE Computer Science Paper 2 sat on 25 May 2023 (J277/02) shows an insertion sort written in pseudocode and asks four "describe" and "explain" questions about it, 2 marks each. There is no code to write. The marks are for saying precisely what the code does.

We do not copy the exam paper here. Open it beside this page: OCR June 2023 J277/02 question paper (PDF). When you have finished, check the mark scheme too.

The question in short

An array called names holds five names, not in order. An outer for loop runs count from 1 to the last index. It sets pos to count. Then an inner while loop runs as long as pos is greater than 0 and the name at pos is less than the name before it. Inside, the two names are swapped using a variable called temp, and pos goes down by 1.

In words: take each name in turn and walk it to the left, one swap at a time, until the name on its left is smaller.

Part (a): what is temp for? (2 marks)

It holds the name at names[pos], so that the value is not lost when it is overwritten during the swap.

Be careful what you say it holds. It holds the name, not the position. The mark scheme refuses answers that say temp stores an index.

Part (b): why is the inner loop condition-controlled? (2 marks)

One mark for each half:

• You do not know in advance how many swaps a name will need. It might already be in place, or it might have to go all the way to the front.
• A condition-controlled loop repeats while a condition is true: here, while the name is still smaller than the one on its left. It stops as soon as the name is in the right place.

Part (c)(i): one difference from a bubble sort (2 marks)

Say something about each sort:

• An insertion sort takes each value once and inserts it into its correct place in the sorted part at the start of the array. A bubble sort repeatedly swaps neighbouring pairs, and needs several passes.
• Or: in an insertion sort the start of the array becomes sorted first. In a bubble sort the end does, because the biggest value bubbles to the top.

"Bubble sort does not do that" is not a second point. The mark scheme says so.

Part (c)(ii): two similarities (2 marks)

Any two: both produce a sorted array; both sort in place, with no second array; both swap values using a temporary variable; both use nested loops; both compare pairs of values; both are slow on large lists compared with a merge sort.

Run it

The same sort in Python. It prints the array after every swap, so you can watch each name walk left. Count the swaps each name needs: that number is what Part (b) is about.

from bugbot import *
connect()

names = ["Kareem", "Sarah", "Zac", "Sundip", "Anika"]
print(names)
for count in range(1, len(names)):
    pos = count
    swaps = 0
    while pos > 0 and names[pos] < names[pos - 1]:
        temp = names[pos]
        names[pos] = names[pos - 1]
        names[pos - 1] = temp
        pos = pos - 1
        swaps = swaps + 1
        print("  ", names)
    print(names[pos], "needed", swaps, "swaps")
print(names)

Now change it

Delete the three lines that use temp and replace them with names[pos] = names[pos - 1] followed by names[pos - 1] = names[pos]. Run it. What has happened to the names, and how does that answer Part (a)?

Questions

What is the purpose of temp in an insertion sort?

It temporarily holds one of the two values being swapped, so that the value is not lost when its place in the array is overwritten.

Why does an insertion sort use a while loop inside a for loop?

The outer for loop takes each item in turn, and the number of items is known. The inner loop moves that item left until it is in place, and the number of moves is not known in advance, so it must be condition-controlled.

What is the difference between an insertion sort and a bubble sort?

An insertion sort builds a sorted section at the start of the list and inserts each new item into its correct place there. A bubble sort passes through the list repeatedly, swapping neighbouring items that are in the wrong order, until a pass makes no swaps.

More from this paper

• Question 1(b) to (d): An assignment, the arithmetic operators, and a do until trace table 7 marks
• Question 2: Syntax and logic errors: correct a loop that should total an array 6 marks
• Question 5(c): An adding game: three random questions and a score 6 marks
• Question 6(b): Sound an alarm when armed AND (door OR window) 4 marks
• Question 6(c): Find the concatenation, a variable, a function call and the constructs 6 marks

Every OCR J277 question we have worked

Learn it step by step

1. F5.8 Insertion sort Algorithms
2. F5.7 Bubble sort Algorithms

This is our own explanation of a published exam question. It is not written or endorsed by OCR, and the question paper and mark scheme remain OCR's copyright. Read them on OCR's site with the links on this page.