ITPEC FE Subject B October 2024 Question 11

Insertion Sort — fill in the missing swap and index update in an insertion sort pseudocode.

The algorithm iterates i from 2 to the array length. For each i, it sets k ← i and uses a while (k > 1) loop to "slide" the element leftward into its correct position.

Inside the while loop:
- If A[k - 1] ≤ A[k], the element is already in place → exit
- Otherwise, A: `swap A[k] and A[k - 1]` — exchange the current element with its left neighbor
- Then B: `k ← k - 1` — move one position left to continue comparing

Why not others:
- (a) Uses i instead of k and overwrites without swapping; k ← k + 1 moves right instead of left
- (b) A[k] ← A[k - 1] overwrites without preserving the original value; swap k and i swaps index variables, not array elements
- (c) A[k - 1] ← A[k] overwrites in the wrong direction; k ← k + 1 moves right
- (d) swap A[i] and A[i - 1] uses the outer loop variable i instead of k, so it always swaps the same pair
- (e) swap A[i] and A[k] swaps with the original position rather than the adjacent element; swap k and i swaps index variables

Key rule: In insertion sort, the inner loop swaps the current element with its immediate left neighbor (A[k] and A[k-1]) and decrements k to continue moving left.

AI-generated — may contain errors