OCR GCSE Computer Science (J277) · Algorithms and programming (Paper 2) › Algorithms › Searching and sorting algorithms
Practise Bubble sort. 11 exam-style questions plus unlimited generated ones on this subtopic, at up to four difficulty levels, with full mark schemes and a progress tracker. Free, no account needed.
Build a paper on this topicWritten for this site in the style of OCR exam questions. They are not taken from real past papers.
Question 1Easy3 marks
(a) Which statement describes how a bubble sort works?
Tick (✓) one box.[1]
- It splits the list in half repeatedly and then merges the parts back together in order
- It compares pairs of adjacent items and swaps them if they are in the wrong order
- It takes each item in turn and inserts it into the correct place in a sorted part of the list
- It checks each item in turn until the required item is found
(b) State how a bubble sort knows that the list is sorted.[1]
(c) Give one advantage of a bubble sort.[1]
Show the answer and mark scheme
(a) Answer: It compares pairs of adjacent items and swaps them if they are in the wrong order
(b) - a pass is completed in which no swaps are made
(c) - simple to understand / code
- sorts the list in place / needs very little extra memory
- quick to check a list that is already sorted (only one pass is needed)
Question 2Medium5 marks
A music app stores a list of 50 000 song titles.
(a) Explain why a bubble sort would not be a good choice for sorting the titles into alphabetical order.[2]
(b) Name a sorting algorithm that would be more efficient for this list.[1]
(c) The titles are already in alphabetical order when a bubble sort is run. State the number of passes the bubble sort makes and explain why.[2]
Show the answer and mark scheme
(a) - it only compares / swaps adjacent items, so a long list needs many passes / a very large number of comparisons
- so it would take a long time / is inefficient for large lists
(c) - one pass
- no swaps are made in the first pass, so the algorithm stops
Question 3Hard8 marks
A programmer has written this procedure to sort an array into ascending order using a bubble sort. It contains errors.
01 procedure sortList(list)
02 for pass = 1 to list.length - 1
03 for i = 0 to list.length - 1
04 if list[i] > list[i + 1] then
05 list[i] = list[i + 1]
06 list[i + 1] = list[i]
07 endif
08 next i
09 next pass
10 endprocedure
(a) The swap on lines 05 and 06 does not work. Explain why, using the two items [8, 3] as an example.[2]
(b) Rewrite lines 05 and 06 so that the swap works correctly.[2]
(c) Identify the other error in the procedure and explain how to correct it.[2]
(d) The procedure always makes list.length − 1 passes. Explain how it could be made more efficient.[2]
Show the answer and mark scheme
(a) - line 05 sets list[0] to 3 so the 8 is overwritten / lost
- line 06 then copies 3 back into list[1], so the list becomes [3, 3]
(b) Answer: temp = list[i]
list[i] = list[i + 1]
list[i + 1] = temp
- stores one of the values in a temporary variable before it is overwritten
- completes the swap correctly using the temporary variable
(c) - line 03: i goes up to list.length − 1, so list[i + 1] is past the end of the array / index out of range
- change line 03 to: for i = 0 to list.length - 2
(d) - use a flag to record whether any swap is made during a pass
- stop sorting when a pass makes no swaps (e.g. replace the outer for loop with a while / do … until loop)
- make each pass one comparison shorter, because the largest remaining item is already in its final place