ITPEC FE Subject B October 2024 Question 11

A: swap A[k] and A[k - 1], B: k ← k - 1 — the inner loop of an insertion sort, which walks the new element left one position at a time.

The outer loop picks the element at position i, and the inner loop moves it left using k. While the left neighbour A[k - 1] is larger than A[k], the two must change places, and k must then follow the element to its new position, one to the left. When the neighbour is not larger, or k reaches 1, the element is in place and the loop ends.

Trace with {3, 1, 2}:

• •i = 2: 3 > 1, swap to {1, 3, 2}, k becomes 1, the while loop ends
• •i = 3: 3 > 2, swap to {1, 2, 3}, k becomes 2; 1 ≤ 2, exit

The output {1, 2, 3} is sorted.

Answer (f)

Why not others:

• •(d) — swaps A[i] and A[i - 1] on every pass, the same pair each time instead of following the element; {3, 2, 1} comes out as {2, 3, 1}
• •(a) and (c) — an assignment instead of a swap overwrites one of the two values, and k ← k + 1 moves k right, away from the exit at k = 1, toward positions past the end of the array
• •(b) — A[k] ← A[k - 1] copies the neighbour over the element being inserted, so its value is lost ({2, 1} becomes {2, 2}); swap k and i does nothing while k = i
• •(e) — on entry k = i, so swap A[i] and A[k] swaps an element with itself and swap k and i swaps equal values; nothing changes and the while loop never ends

Key rule: In an inner loop, check that every exchange keeps both values and that the index moves toward the loop's exit condition; a plain assignment in place of a swap silently duplicates an element.

Sorting · AI-written, may contain errors