IPA FE Subject B 2023 Question 3

Topic: Sorting

A question IPA Japan published in 令和５年度 基本情報技術者試験 科目B 公開問題 問3, translated into English. ITPEC is based on the same exams.

From the answer group below, select the correct answer to be inserted into blank in the description. Here, the array index starts at 1.

The following procedure sort sorts the elements of the global integer-type array data, from the index given by the argument first to the index given by the argument last, in ascending order. Here, first < last. When the procedure sort is called as sort(1, 5), the output when the line /*** α ***/ is executed for the first time is “blank”.

[Program]
global: integer []: data ← {2, 1, 3, 5, 4}
○ sort(integer: first, integer: last)
integer: pivot, i, j
pivot ← data[the quotient of (first + last) ÷ 2]
i ← first
j ← last
while (true)
while (data[i] < pivot)
i ← i + 1
endwhile
while (pivot < data[j])
j ← j - 1
endwhile
if (i ≥ j)
terminate the iteration process
endif
swap the values of data[i] and data[j]
i ← i + 1
j ← j - 1
endwhile
output the values of all elements of data in the order of the indexes, separated by spaces /*** α ***/
if (first < i - 1)
sort(first, i - 1)
endif
if (j + 1 < last)
sort(j + 1, last)
endif

Answer group

Explanation

2 1 3 5 4 — the α line first runs at the end of the first partitioning pass of sort(1, 5), before either recursive call.

The pivot is data[3] = 3, since the quotient of (1 + 5) ÷ 2 is 3. In the first pass of the outer loop, i moves right past the elements less than 3 and j moves left past the elements greater than 3:

  • •i: data[1] = 2 and data[2] = 1 are less than 3; data[3] = 3 is not, so i stops at 3
  • •j: data[5] = 4 and data[4] = 5 are greater than 3; data[3] = 3 is not, so j stops at 3

Now i ≥ j, so the loop ends before any swap, and the α line outputs data unchanged: 2 1 3 5 4. Only then do sort(1, 2) (output 1 2 3 5 4) and sort(4, 5) (output 1 2 3 4 5) run.

Answer (d)

Why not others:

  • •(a) 1 2 3 4 5 — the fully sorted array, printed by the third α line, at the end of sort(4, 5)
  • •(b) 1 2 3 5 4 — the second α line's output, after sort(1, 2) swaps 2 and 1
  • •(c) 2 1 3 4 5 — would need sort(4, 5) to have run first; at the first α line neither recursive call has run yet

Key rule: In a recursive quicksort, a line after the partition loop but before the recursive calls sees the array after one partition only, and that partition moves elements only by its swaps.

Sorting · AI-written, may contain errors

Practice this exam

This question comes from the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.