Studyledge

Advanced Algorithms and Recursion: Question 8

Syllabus 19.1

Structured A2 8 marks

A programmer writes the following procedure to sort an array of six race times, in seconds, into ascending order using insertion sort.

PROCEDURE InsertionSort(Arr : ARRAY[1:6] OF INTEGER)
    DECLARE i, j, Key : INTEGER
    FOR i ← 2 TO 6
        Key ← Arr[i]
        j ← i - 1
        WHILE (j >= 1) AND (Arr[j] > Key) DO
            Arr[j + 1] ← Arr[j]
            j ← j - 1
        ENDWHILE
        Arr[j + 1] ← Key
    NEXT i
ENDPROCEDURE

InsertionSort is called on Arr = [29, 10, 14, 37, 8, 22] (index 1 to index 6).

(a) State the contents of Arr, in order, immediately after the outer loop iteration where i = 3 completes (i.e. once Key = 14 has been inserted into its correct position). [2]

(b) State the contents of Arr, in order, immediately after the outer loop iteration where i = 5 completes, showing which values are shifted rightward by the WHILE loop to make room for Key = 8. [4]

(c) State the final, fully sorted contents of Arr once the procedure completes, and explain one way in which insertion sort's method of placing each Key differs from bubble sort's method of repeatedly comparing and swapping adjacent elements. [2]

Show worked solution Hide worked solution

Worked solution

Part (a): Tracing outer loop iterations i = 2 and i = 3

Insertion sort takes each element in turn (Key) and shifts every larger element already to its left one position to the right, until it finds Key’s correct position.

i = 2: Key = Arr[2] = 10, j = 1. Arr[1] = 29 > 10, so Arr[2] ← 29 and j ← 0. Now j >= 1 is false, so the loop stops, and Arr[1] ← Key = 10. Array: [10, 29, 14, 37, 8, 22]

i = 3: Key = Arr[3] = 14, j = 2. Arr[2] = 29 > 14, so Arr[3] ← 29 and j ← 1. Now Arr[1] = 10 > 14 is false, so the loop stops, and Arr[2] ← Key = 14. Array: [10, 14, 29, 37, 8, 22]

[2 marks]: [1] for correctly tracing the shift of 14 past 29, [1] for the correct resulting array [10, 14, 29, 37, 8, 22].

Part (b): Tracing through outer loop iteration i = 5

i = 4: Key = Arr[4] = 37, j = 3. Arr[3] = 29 > 37 is false, so the WHILE loop does not run, and Arr[4] ← Key = 37 (unchanged). Array: [10, 14, 29, 37, 8, 22]

i = 5: Key = Arr[5] = 8, j = 4.

StepCondition checkActionj after
1Arr[4] = 37 > 8? YesArr[5] ← 373
2Arr[3] = 29 > 8? YesArr[4] ← 292
3Arr[2] = 14 > 8? YesArr[3] ← 141
4Arr[1] = 10 > 8? YesArr[2] ← 100
5j >= 1? No, loop stopsArr[1] ← Key = 8,

The values 37, 29, 14 and 10 are each shifted one position to the right, and Key = 8 is placed at index 1.

Array: [8, 10, 14, 29, 37, 22]

[4 marks]: [1] for correctly identifying that i = 4 leaves the array unchanged, [2] for correctly tracing all four rightward shifts (37, 29, 14, 10), [1] for the correct resulting array [8, 10, 14, 29, 37, 22].

Part (c): The final array and comparing insertion sort with bubble sort

i = 6: Key = Arr[6] = 22, j = 5. Arr[5] = 37 > 22, so Arr[6] ← 37, j ← 4. Arr[4] = 29 > 22, so Arr[5] ← 29, j ← 3. Arr[3] = 14 > 22 is false, so the loop stops, and Arr[4] ← Key = 22.

Final array: [8, 10, 14, 22, 29, 37], sorted into ascending order.

Insertion sort works by treating the left-hand part of the array as an already-sorted section, and repeatedly taking the next element (Key) and shifting only the elements in that sorted section that are greater than Key one place to the right, before inserting Key directly into the gap this creates. Bubble sort instead works by repeatedly scanning through the (sub)list from one end to the other, comparing each pair of adjacent elements and swapping them if they are in the wrong order, requiring multiple full passes over the array before it is fully sorted.

[2 marks]: [1] for the correct final sorted array, [1] for a valid explanation of how insertion sort’s shift-and-insert method differs from bubble sort’s adjacent compare-and-swap method.

Final answers

  • (a) After i = 3: [10, 14, 29, 37, 8, 22]
  • (b) After i = 5: [8, 10, 14, 29, 37, 22]
  • (c) Final sorted array: [8, 10, 14, 22, 29, 37]. Insertion sort shifts larger elements of an already-sorted section rightward to insert each Key directly, rather than repeatedly comparing and swapping only adjacent pairs across full passes as bubble sort does.