Level:
Correct: 0
Incorrect: 0
Marks: 0/0
Exam Practice
Course:
Topics:
OCR GCSE Computer Science (Paper 2) Smart practice A mixed round aimed at your weak spots
Unit 1
Algorithms
Unit 2
Programming fundamentals
Unit 3
Producing robust programs
Unit 4
Boolean logic
Unit 5
Programming languages and IDEs
Unit 6
Practical programming (Section B)
Avg
score:
–
Topics
done:
0/31

Bubble sort

Practise 28 exam-style questions on Bubble sort for OCR GCSE Computer Science (Paper 2). Write your answer as you would in the exam and get it marked in seconds against the mark scheme, point by point, with the Study Helper on hand if you get stuck.

  • 28 questions
  • 1–6 marks each
  • Instant marking
  • No sign-up needed
20 questions, marked as you go

Sample questions with model answers

Here are 4 of the questions in this topic, each with a model answer, an explanation of why it earns the marks and the mark scheme an examiner would use.

Question 1

2 marks

A bubble sort is used to sort a list of 8 items.

State how many comparisons are made in the first pass, and explain how the algorithm knows when the list is sorted.

Model answer

7 comparisons: items 1 and 2, 2 and 3, and so on up to items 7 and 8. The algorithm knows the list is sorted when it completes a whole pass without making any swaps.

Explanation

A list of n items has n - 1 adjacent pairs, so a full pass makes n - 1 comparisons. The algorithm cannot see that the list is sorted; it uses a flag that records whether any swap happened during a pass, and stops when a pass makes none.

Mark scheme
  1. 1 mark

    7

  2. 1 mark

    when a complete pass is made with no swaps

    accept 'when the swapped flag is still False at the end of a pass'. Also accept 'after 7 (n - 1) passes, because each pass puts one more item in its final place'. Do not accept 'when the list is in order' with no explanation of how this is detected.

Question 2

2 marks

The table shows records of five players and their scores in a quiz.

A bubble sort is used to sort the records into descending order of score (highest first). When two records are swapped, the whole record (player and score) moves.

Give the order of the players' names after the first pass and after the second pass.

Quiz scores. Table with columns "Index", "Player", "Score". Index: 0; Player: Mo; Score: 64 | Index: 1; Player: Ana; Score: 81 | Index: 2; Player: Raj; Score: 57 | Index: 3; Player: Tia; Score: 90 | Index: 4; Player: Ben; Score: 72.

Model answer

Pass 1 (scores 81, 64, 90, 72, 57): Ana, Mo, Tia, Ben, Raj
Pass 2 (scores 81, 90, 72, 64, 57): Ana, Tia, Ben, Mo, Raj

Explanation

The scores decide every comparison, and for descending order a pair is swapped when the first score is lower than the second. In pass 1, Raj's 57, the lowest score, ends up last; in pass 2, Mo's 64 moves into fourth place. Each name stays with its own score because the whole record is swapped.

Mark scheme
  1. 1 mark

    after pass 1: Ana, Mo, Tia, Ben, Raj

    Scores in this order: 81, 64, 90, 72, 57. Accept the scores shown alongside the names.

  2. 1 mark

    after pass 2: Ana, Tia, Ben, Mo, Raj

    Scores: 81, 90, 72, 64, 57. Follow through from an incorrect pass 1 if pass 2 is a correct descending pass of it.

Question 3

3 marks

The program below should sort the array points into ascending order and then output the sorted values.

01array points = [35, 12, 48, 20]
02swapped = True
03while swapped == True
04    swapped = False
05    for i = 0 to 2
06        if points[i] < points[i + 1] then
07            temp = points[i]
08            points[i] = points[i + 1]
09            points[i + 1] = temp
10            swapped = True
11        endif
12    next i
13endwhile
14for i = 0 to 3
15    print(points[i])
16next i

When the program is run it outputs 48, 35, 20, 12 (one value per line).

Identify the line that contains the error, explain what the error does, and write the corrected line.

Model answer

Line 06 is wrong. It swaps two items when the first is smaller than the second, which moves smaller items to the end, so the list is sorted into descending order instead of ascending.

Corrected line 06: if points[i] > points[i + 1] then

Explanation

The comparison in a bubble sort decides the order: swap when the first item is bigger for ascending order, and when it is smaller for descending order. This is a logic error, not a syntax error: the program runs, but gives the wrong result. Testing with a small list soon shows it up.

Mark scheme
  1. 1 mark

    line 06

    Award this mark if the corrected line clearly identifies the line.

  2. 1 mark

    it swaps the items when the first is smaller than the second, so it sorts into descending order

  3. 1 mark

    if points[i] > points[i + 1] then

    accept points[i + 1] < points[i]. Do not accept >=: if two values are equal they would be swapped in every pass, so swapped would always be True and the loop would never end.

Question 4

4 marks

This program sorts the array data using a bubble sort. Every pass compares every adjacent pair.

array data = [5, 1, 4, 2, 8, 3]
swapped = True
while swapped == True
    swapped = False
    for i = 0 to 4
        if data[i] > data[i + 1] then
            temp = data[i]
            data[i] = data[i + 1]
            data[i + 1] = temp
            swapped = True
        endif
    next i
endwhile

Describe how the program could be changed so that it makes fewer comparisons, and explain why the changed program still sorts correctly. State the total number of comparisons made by the original program and by your changed program when sorting this list.

Model answer

Use a variable, for example last = 4, as the end value of the for loop (for i = 0 to last) and decrease last by 1 after each pass. This works because each pass moves the largest remaining item to its final place at the end, so those items never need to be compared again.

The list needs 4 passes (the fourth makes no swaps).
Original program: 4 x 5 = 20 comparisons.
Changed program: 5 + 4 + 3 + 2 = 14 comparisons.

Explanation

After pass 1 the largest item is at the end, after pass 2 the two largest are in place, and so on, so pass k only needs to look at the first n - k + 1 items. The lists after each pass are exactly the same as before; only wasted comparisons are removed. The passes here give 1, 4, 2, 5, 3, 8, then 1, 2, 4, 3, 5, 8, then 1, 2, 3, 4, 5, 8, then a pass with no swaps.

Mark scheme
  1. 1 mark

    make each pass one comparison shorter than the one before / reduce the end value of the for loop by 1 after each pass (e.g. use a variable that starts at 4 and is decreased)

  2. 1 mark

    after each pass the largest remaining item is in its final place at the end, so comparing the items that are already in place is not needed

  3. 1 mark

    original: 20 comparisons

    4 passes (including the final pass with no swaps) of 5 comparisons

  4. 1 mark

    changed: 14 comparisons

    5 + 4 + 3 + 2 over the same 4 passes. Follow through for a different valid improvement if the student's count is correct for it.

Ready to try the rest? Every answer you write is marked against the mark scheme, so you can see exactly where the marks are.

Study Helper Hints first, answers after you try

Stuck on this one? Ask for a hint and I’ll point you in the right direction, without giving the answer away. Once you’ve checked your answer, I’ll show you how the marks are awarded.