IPA IP 2023 Question 60

Topic: Algorithm and Programming

A question IPA Japan published in 令和5年度 ITパスポート試験 公開問題 問60, translated into English. ITPEC is based on the same exams.

The procedure printArray sorts the elements of the array integerArray and outputs them. Which of the following is the output when the procedure printArray is called? Here, the array index starts at 1.

[Program]
○ printArray()
integer: n, m
integer []: integerArray ← {2, 4, 1, 3}
for (increase n from 1 to (the number of elements in integerArray − 1) by 1)
for (increase m from 1 to (the number of elements in integerArray − n) by 1)
if (integerArray[m] > integerArray[m + 1])
swap the values of integerArray[m] and integerArray[m + 1]
endif
endfor
endfor
output all the elements of integerArray from the first one in order, separated by commas

Explanation

1,2,3,4 — the program is a bubble sort that swaps neighbours when the left one is larger, so it sorts the array into ascending order.

Trace from {2, 4, 1, 3} (4 elements, so n runs 1 to 3 and m runs 1 to 4 − n):

nComparisons and swapsArray after the pass
12 > 4 no; 4 > 1 swap; 4 > 3 swap2,1,3,4
22 > 1 swap; 2 > 3 no1,2,3,4
31 > 2 no1,2,3,4

Each pass carries the largest remaining value to the end, which is why the inner loop stops one element earlier each time.

Answer (a)

Why not others:

  • •(b) 1,3,2,4 and (c) 3,1,4,2 — neither is a state the array passes through; after the first pass it is already 2,1,3,4, with 4 at the end
  • •(d) 4,3,2,1 — descending order, which a swap on < would give; this program swaps when the left element is greater

Key rule: In a bubble sort, swapping when a[m] > a[m + 1] sorts ascending, and after pass n the last n elements are in their final places.

Algorithm and Programming · 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.