OCR GCSE Computer Science sample Paper 2, Question 6: a bubble sort and a binary search

OCR J277/02 sample assessment material, Question 6: show the stages of a bubble sort on six words, then the stages of a binary search for zebra in nine sorted words. Both worked pass by pass, with programs that print every stage.

Past paper questionOCR J277/02Sample Paper 28 marksExplain

Question 6 of OCR's sample assessment material for GCSE Computer Science Paper 2 (J277/02) asks you to show two standard algorithms on real data: 4 marks each. Words instead of numbers, which is where people slip.

We do not copy the paper here. Open it beside this page: OCR J277/02 sample question paper and mark scheme (PDF). The mark scheme is in the same document.

Part (a): bubble sort crime, bait, fright, victory, nibble, loose

A bubble sort compares neighbours and swaps them when they are out of order. Words compare alphabetically. The mark scheme accepts one row per pass, with all of a pass's swaps shown together.

Pass 1 in detail: crime and bait swap; crime and fright stay; fright and victory stay; victory and nibble swap; victory and loose swap. Pass 2: only nibble and loose swap. A third pass makes no swaps, so the sort is finished.

One mark for each row after the first, and you can show swaps one at a time instead.

Part (b): binary search for zebra in nine sorted words

amber, house, kick, moose, orange, range, tent, wind, zebra.

1. The middle of nine is the fifth: orange. Zebra is greater, so discard the left half. Left: range, tent, wind, zebra.
2. With four items there is no exact middle. Take tent (or wind). Zebra is greater, so discard the left. Left: wind, zebra.
3. Compare with wind. Greater again. Left: zebra.
4. Compare with zebra. Found.

The four marks: comparing with orange; greater, so taking the right side; a further comparison; and finding zebra by the same method. Which middle you choose from an even number is up to you, so long as you say.

Where the marks are lost

• Sorting by length. "bait" comes before "crime" because b is before c, not because it is shorter.
• Showing only the sorted list in part (a). Each row is a mark.
• Starting the search at amber. That is a linear search. Binary search starts in the middle.
• Not saying which side is kept and why. "Zebra comes after orange, so the left half is discarded" is the second mark.

Run it

A bubble sort that prints after every pass, then a binary search that prints every comparison.

from bugbot import *
connect()

words = ["crime", "bait", "fright", "victory", "nibble", "loose"]
print(words)
swapped = True
passes = 0
while swapped:
    swapped = False
    for i in range(len(words) - 1):
        if words[i] > words[i + 1]:
            words[i], words[i + 1] = words[i + 1], words[i]
            swapped = True
    passes = passes + 1
    print("pass", passes, words)

data = ["amber", "house", "kick", "moose", "orange", "range", "tent", "wind", "zebra"]
target = "zebra"
low = 0
high = len(data) - 1
found = False
while low <= high and not found:
    mid = (low + high) // 2
    print("compare with", data[mid])
    if data[mid] == target:
        found = True
    elif target > data[mid]:
        low = mid + 1
    else:
        high = mid - 1
print("found:", found)

Questions

What is the answer to OCR J277 sample Paper 2 Question 6(a)?

After pass 1: bait, crime, fright, nibble, loose, victory. After pass 2: bait, crime, fright, loose, nibble, victory. Pass 3 makes no swaps.

What is the answer to Question 6(b)?

Compare zebra with the middle word, orange. Zebra is greater, so discard the left half. Compare with tent (or wind), greater again, then with wind, then find zebra.

How are words compared in a sort?

Alphabetically, letter by letter from the left. "bait" is less than "crime" because b comes before c. Length does not matter unless one word is the start of the other.

More from this paper

• Question 2: Complete a comparison of two numbers, then write a loop that doubles inputs 10 marks
• Question 4: Usernames from a flowchart, then an algorithm for teachers and students 8 marks
• Question 8(b) to (d): A range check with OR and its tests, index a 2D array, refine repeated lines into a loop 10 marks
• Question 8(e), (g): A while loop trace table, a function that returns minutes, and a flowchart as code 14 marks

Every OCR J277 question we have worked · Guide: Linear search and binary search explained

Learn it step by step

1. F5.7 Bubble sort Algorithms
2. F5.6 Binary search 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.