An array Scores contains 8 test scores that need to be sorted in ascending order using an insertion sort. (a) Describe how the insertion sort algorithm work...
Question 1 Report
An array Scores contains 8 test scores that need to be sorted in ascending order using an insertion sort.
(a) Describe how the insertion sort algorithm works. [3]
(b) Write pseudocode for an insertion sort to sort the array Scores in ascending order. [5]
(c) The initial array is shown below. Show the state of the array after the first three passes of the insertion sort. [2]
| Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| Initial | 45 | 12 | 78 | 33 | 56 | 21 | 90 | 67 |
| After pass 1 | ||||||||
| After pass 2 | ||||||||
| After pass 3 |
Answer Details
(a) Insertion sort maintains a sorted portion at the beginning of the array and an unsorted portion after it. It takes the first element from the unsorted portion (the "key") and compares it with elements in the sorted portion, shifting elements right to create space. [1] It inserts the key into its correct position within the sorted portion. [1] This process repeats, growing the sorted portion by one element each pass, until all elements are sorted. [1] [3]
(b) The pseudocode for insertion sort on an 8-element array:
DECLARE Key : INTEGER
DECLARE i : INTEGER
DECLARE j : INTEGER
FOR i <- 2 TO 8
Key <- Scores[i]
j <- i - 1
WHILE j >= 1 AND Scores[j] > Key DO
Scores[j + 1] <- Scores[j]
j <- j - 1
ENDWHILE
Scores[j + 1] <- Key
NEXT iThe outer loop starts from 2 (the first element is already "sorted") [1]. Key saves the element being inserted [1]. The WHILE loop finds the correct position by shifting larger elements right [1]. Elements are shifted, not swapped [1]. The key is placed at its correct position [1]. [5]
(c) Starting with [45, 12, 78, 33, 56, 21, 90, 67]:
| Pass | Key | Action | Array after pass |
|---|---|---|---|
| 1 | 12 | 12 < 45, shift 45 right, insert 12 at position 1 | [12, 45, 78, 33, 56, 21, 90, 67] |
| 2 | 78 | 78 > 45, already in correct position, no shift needed | [12, 45, 78, 33, 56, 21, 90, 67] |
| 3 | 33 | 33 < 78, shift 78 right; 33 < 45, shift 45 right; 33 > 12, insert at position 2 | [12, 33, 45, 78, 56, 21, 90, 67] |
[2]
Download The App On Google Playstore
Everything you need to excel in your exams
