OCR J277 - Sorting Algorithms Revision

1 [4 Marks]

List: [ "Dave", "Alan", "Cian", "Ben" ]
(a) Show list after First Pass (Bubble Sort).
(b) Why is a 2nd pass needed even if it looks sorted?

Bubble Sort rule: Largest item "bubbles" to the end in the first pass.

✅ Mark Scheme

(a) [ "Alan", "Cian", "Ben", "Dave" ] (Dave at end).

(b) The algorithm doesn't "know" it's sorted until it does a full pass with zero swaps.

Score:

2 [5 Marks]

List: [ 12, 5, 18, 1, 9 ]
(a) Show list after the second insertion (processing 18).
(b) Describe steps to insert '1'.

Hint (a): Only the first 3 items (Indices 0, 1, 2) are sorted.
Hint (b): Compare -> Shift -> Insert.

(a) List State:

✅ Mark Scheme

(a) [ 5, 12, 18, 1, 9 ]

(b) Compare 1 with 18, 12, 5. Shift them right. Insert 1 at index 0.

Score:

3 [5 Marks]

List: [ 15, 3, 9, 12, 6, 2 ]
(a) Show list when completely divided.
(b) Show steps to merge back.

✅ Mark Scheme

(a) [15] [3] [9] [12] [6] [2] (All separate).

(b)
1. Pairs: [3,15] [9,12] [2,6]
2. Groups: [3,9,12,15] [2,6]
3. Final: [2,3,6,9,12,15]

Score:

4 [4 Marks]

Advantage of Merge Sort vs Bubble Sort.

✅ Mark Scheme

Merge: Faster/Efficient on large lists (O(n log n)).

Bubble: Easier to code, less memory usage.

Score:

5 [4 Marks]

01 array scores = [9, 2, 5, 1] 02 n = scores.length 03 swapped = True 04 while swapped == True 05 swapped = False 06 for i = 0 to n - 1 07 if scores[i] < scores[i+1] then 08 temp = scores[i] 09 scores[i] = scores[i+1] 10 scores[i+1] = temp 11 endif 12 next i 13 endwhile

(a) Line number with wrong comparison (for Ascending)?
(b) Line number causing "Index Out of Bounds"?
(c) Purpose of `swapped`?

(a) Look at line 07. Are we checking if it's bigger or smaller?
(b) Look at line 06. If i is n-1, what is i+1?

✅ Mark Scheme

(a) Line 07 (Should be > not <).< /p>

(b) Line 06 (Should be n-2 or similar, i+1 goes out of bounds).

(c) Efficiently stops the loop if the list is already sorted.

Score:

6 [6 Marks]

Write Insertion Sort pseudocode. Logic for: Compare, Shift, Insert.

Structure:
For i = 1 to end
current = data[i]
j = i - 1
While j >= 0 AND data[j] > current
Shift right...
Insert...

✅ Mark Scheme

for i = 1 to data.length - 1
  current = data[i]
  j = i - 1
  while j >= 0 AND data[j] > current
    data[j+1] = data[j]
    j = j - 1
  endwhile
  data[j+1] = current
next i

Score:

7-10 -> Scenarios [10 Marks]

7. Adding 5 items to sorted list: Which algo? Why? (3)
8. How Merge Sort uses Decomposition? (2)
9. Bubble Sort Loop Condition? (2)
10. Trace Insertion Sort for [4, 3, 5] Pass 2. (3)

✅ Mark Scheme

7. Insertion Sort. Efficient for adding small number of items to sorted list.

8. Breaks list down into smaller sub-lists (Divide/Decompose).

9. while swapped == True

10. Pass 2: Compare 4 > 5 (False/No). No Shift. Array remains [3, 4, 5].

Score:

Topic 2.1.3: Sorting Algorithms