Consider the following sorting procedure: Which sorting algorithm is implemented by this...
Ion technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Consider the following sorting procedure:
procedure sort(A: list of sortable items)
n = length(A)
for i = 1 to n - 1 do
j = i
while j > 0 and A[j-1] > A[j] do
swap(A[j], A[j-1])
j = j - 1
end while
end for
end procedure
Which sorting algorithm is implemented by this procedure, and what is its worst-case time complexity?
Show answer & explanation
The algorithm iterates through the list and, for each element, shifts it backward (via swaps) until it reaches its correct sorted position relative to the elements before it. This is the defining mechanism of Insertion Sort, which has a quadratic worst-case time complexity when the input is sorted in reverse order.
Step-by-step Derivation:
Step 1: Analyze the algorithm structure. The outer loop for i = 1 to n - 1 iterates through the array starting from the second element. The inner while loop while j > 0 and A[j-1] > A[j] compares the current element A[j] with its predecessor A[j-1] and swaps them if they are out of order, effectively 'inserting' the element into the sorted prefix of the array.
Step 2: Identify the algorithm. This specific pattern of building a sorted sequence one element at a time by shifting elements is the implementation of Insertion Sort.
Step 3: Determine worst-case time complexity. In the worst case (where the input array is sorted in reverse order), for every index i, the inner loop runs i times. The total number of comparisons/swaps is $\sum_{i=1}^{n-1} i = \frac{(n-1)n}{2}$, which simplifies to $O(n^2)$.
Step 4: Compare with options. Option A correctly identifies both the algorithm (Insertion Sort) and the complexity ($O(n^2)$).