OCR GCSE Computer Science (J277) · Algorithms and programming (Paper 2) › Algorithms › Searching and sorting algorithms
Practise Insertion sort. 12 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.
Cover the answers and test yourself. The app has these as flashcards that come back just before you'd forget them.
State the list after 2 has been inserted into the sorted part.
2, 7, 9, 4
Sample questions
Written for this site in the style of OCR exam questions. They are not taken from real past papers.
Question 1Easy4 marks
(a) A sorting algorithm takes each item in turn and puts it into the correct position in the sorted part of the list. Which algorithm is this? Tick (✓) one box.[1]
Bubble sort
Insertion sort
Merge sort
Binary search
(b) Describe how an insertion sort works.[3]
Show the answer and mark scheme
(a)Answer: Insertion sort
(b)
the first item is treated as a sorted list / the sort starts with the second item
each item in turn is taken from the unsorted part of the list
and inserted into the correct position in the sorted part (larger items are moved one place to the right)
this repeats until the last item has been inserted
Question 2Medium6 marks
The algorithm below sorts the array items into ascending order using an insertion sort. Three parts are missing.
01 for i = 1 to items.length - 1
02 current = items[i]
03 pos = i
04 while pos > 0 AND items[pos - 1] > ....(1)....
05 items[pos] = ....(2)....
06 pos = pos - 1
07 endwhile
08 items[pos] = ....(3)....
09 next i
(a) Write the missing code for each of the gaps (1) to (3).[3]
(b) Explain why the loop on line 01 starts at 1 and not at 0.[1]
(c) Explain why the condition pos > 0 is needed on line 04.[2]
Show the answer and mark scheme
(a)Answer: (1) current (2) items[pos - 1] (3) current
(1) current
(2) items[pos - 1]
(3) current
(b)
the first item (position 0) on its own is already a sorted list / there is nothing before it to compare with
(c)
when the current item is smaller than every item in the sorted part, pos reaches 0
without the check, items[pos - 1] would be items[−1], which is outside the array / causes an error
Question 3Hard7 marks
A shop keeps a list of 500 product codes in order. Each day a few new codes are added to the end of the list, and the list is then sorted again.
(a) Explain why an insertion sort is a good choice for sorting this list.[3]
(b) An insertion sort is used on the list [3, 5, 8, 12, 14, 6]. State the total number of comparisons it makes. Show your working.[2]
(c) A bubble sort that compares every adjacent pair in each pass, and stops after a pass with no swaps, is used on the same list instead. State the number of passes it makes and the total number of comparisons.[2]
Show the answer and mark scheme
(a)
most of the list is already in order
each item that is already in the right place needs only one comparison
so only the few new codes need to be moved / very few comparisons and moves are needed overall
it sorts the list in place, so little extra memory is needed
(b)Answer: 8 (1 each for 5, 8, 12 and 14; 4 for 6)