令和5年度 問60
アルゴリズムとプログラミング
整列に関する問題
手続printArrayは，配列integerArrayの要素を並べ替えて出力する。手続printArrayを呼び出したときの出力はどれか。ここで，配列の要素番号は1から始まる。
〔プログラム〕
○printArray()
整数型: n, m
整数型の配列: integerArray ← {2, 4, 1, 3}
for (n を 1 から (integerArray の要素数 － 1) まで 1 ずつ増やす)
for (m を 1 から (integerArray の要素数 － n) まで 1 ずつ増やす)
if (integerArray[m] ＞ integerArray[m ＋ 1])
integerArray[m] と integerArray[m ＋ 1] の値を入れ替える
endif
endfor
endfor
integerArray の全ての要素 を先頭から順にコンマ区切りで出力する- ア1,2,3,4
- イ1,3,2,4
- ウ3,1,4,2
- エ4,3,2,1
答えと解説を見る
✓ これが正解ア1,2,3,4
解説
隣を比べて入れ替える手続なので、昇順に並び替わります。
擬似言語で書かれたこの手続は、配列を小さい順に整列させるものです。配列の先頭から順に隣り合う二つを比べ、左のほうが大きければ入れ替える、という走査を繰り返します。一度走査するたびに、まだ確定していない範囲の中で最も大きい値が右端へ送られるので、内側の繰返しの範囲が一つずつ狭まっていきます。これを要素数から1を引いた回数だけ行えば、全体が小さい順に並びます。初期値は2、4、1、3です。一度目の走査で2、1、3、4となり、二度目で1、2、3、4となって、三度目では入れ替えが起きません。並び終わった後も残りの走査は行われますが、入れ替えが起きないだけで結果は変わりません。よって出力は1,2,3,4です。
ほかの選択肢はなぜ違うのか
- イ1,3,2,4：1,3,2,4は、この手続では途中にも最後にも現れない並びです。初期値から走査すると2,1,4,3、2,1,3,4と変わり、二度目の走査で1,2,3,4になります。3と2が隣で逆に並ぶ形はどの時点にも現れないので、途中で止めたとしてもこの並びにはなりません。
- ウ3,1,4,2：3,1,4,2は、初期値の並びとも、並べ替えた結果とも合いません。比べているのは隣り合う要素どうしなので、離れた位置の値が飛び越えて入れ替わることはこの手続では起こりません。手続を一巡ずつ紙の上でたどれば、この並びが現れないことを自分で確かめられます。
- エ4,3,2,1：4,3,2,1は、大きい順に並べた形です。この手続は左のほうが大きいときに入れ替えるので、大きい値が右へ送られ、結果は小さい順になります。比べる向きを逆に読むとこの並びになります。
出典：令和5年度 ITパスポート試験 問60（改変：原典の図表をテキストに書き起こした）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）