令和5年度の科目B、その3問目です。sort という名前と、自分自身を呼び出す行が2つ見えるので、身構える人が多い問題です。ところが訊かれているのは α の行を最初に実行したときの出力で、そこへ着くまでに sort(…) の行には1度も来ません。この記事では、並べ替えのやり方を知らないまま、書いてあるとおりに i と j を動かすだけで、解答群に頼らずに答えを書くところまで進みます。
出題
まず原文のまま読んでみてください。記号の読み方は次の節にまとめてありますので、読めなくてもここでは問題ありません。
出典：令和5年度 基本情報技術者試験 科目B 公開問題 問3
次の記述中の に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は1 から始まる。
次の手続sort は，大域の整数型の配列data の，引数first で与えられた要素番号から引数last で与えられた要素番号までの要素を昇順に整列する。ここで，first ＜ last とする。手続sort をsort(1, 5) として呼び出すと，/*** α ***/ の行を最初に実行したときの出力は“ ”となる。
〔プログラム〕
大域: 整数型の配列: data ← {2, 1, 3, 5, 4}
○sort(整数型: first, 整数型: last)
整数型: pivot, i, j
pivot ← data[(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)
繰返し処理を終了する
endif
data[i]とdata[j]の値を入れ替える
i ← i ＋ 1
j ← j － 1
endwhile
dataの全要素の値を要素番号の順に空白区切りで出力する /*** α ***/
if (first ＜ i － 1)
sort(first, i － 1)
endif
if (j ＋ 1 ＜ last)
sort(j ＋ 1, last)
endif
解答群
ア 1 2 3 4 5イ 1 2 3 5 4
ウ 2 1 3 4 5エ 2 1 3 5 4
答えだけ先に見る
正解は エ（2 1 3 5 4）です。
この問題に出てくる記号
読めない記号があったときだけ開いてください。いま読めればいいのは9つだけです。
擬似言語の記号 9コ の読み方をひらく
| 書き方 | 読み方 |
|---|---|
大域: |
その配列や変数が、どの手続からでも読み書きできることを表します。data は引数で渡されていませんが、大域なので sort の中からそのまま読み書きできます |
○sort(整数型: first, 整数型: last) |
手続 sort の宣言です。first と last は引数で、呼び出しの sort(1, 5) では 1 が first、5 が last に入ります |
整数型: pivot, i, j |
整数を入れる箱を3つ用意する、という宣言です。pivot・i・j はこの問題が付けただけの名前で、覚える必要はありません |
data[3] |
配列 data の3番目の値です。この問題では要素番号が 1 から始まります |
÷ 2 の商 |
2 で割った商です。あまりは捨てます（7 ÷ 2 の商 は 3） |
if (条件式)〜 endif≧ |
条件式が真のときだけ、あいだの行を実行します。偽なら、あいだを飛ばして endif の次の行へ進みます。≧ は「以上」で、3 ≧ 3 のように同じ値でも真になります |
while (条件式)〜 endwhile |
条件式が真であるあいだ、あいだの行を繰り返します。偽になった瞬間に、その繰返しから抜けます。条件式が最初から偽なら、あいだの行は1度も実行されません |
while (true)繰返し処理を終了する |
true はいつでも真という意味なので、この繰返しは自分から終わりません。抜ける道は 繰返し処理を終了する の1行だけで、この行に来ると、いま入っている繰返しを抜けて endwhile の次の行へ進みます |
/*** α ***/ |
注釈です。実行されません。この問題では、その行に付けた名前として問題文から参照されています |
記号でつまずいたら、下の教科書から、先にそこだけ読んでください（G7 のような番号は、当サイトの擬似言語の教科書の第何回かを表します）。
出力するのは、いつの data か
この問題が訊いているのは「並べ替えた結果」ではありません。α の行を最初に実行したときの出力です。ですから最初にやることは、α の行がプログラムのどこにあるかを見ることになります。
〔プログラム〕α の行と、その下にある2つの sort の呼び出し
dataの全要素の値を要素番号の順に空白区切りで出力する /*** α ***/ if (first ＜ i － 1) sort(first, i － 1) endif if (j ＋ 1 ＜ last) sort(j ＋ 1, last) endif
※ 上の〔プログラム〕からの抜粋です（1字も変えていません）。
α の行は、while (true) の endwhile のすぐ下にあります。そして sort が自分自身を呼び出す2つの行は、そのさらに下です。
出力するのは、いつの data か
α を最初に実行するのは、sort(…) の行に1度も来ていない時点です。つまり while (true) を1回抜けたところまでを追えば、答えが出ます。自分自身を呼び出す部分は、今回は考えなくてかまいません。
手で動かす ── i と j を動かして、空欄に入るものを決める
では sort(1, 5) を、書いてあるとおりに動かします。first は 1、last は 5 です。各段の上に、その段で実行する行を〔プログラム〕から抜き出して置きました。
i と j は、どこで止まるか
各段の上のコードは、その段で実行する行です（上の〔プログラム〕から抜き出したもので、1字も変えていません）。▲ が、i か j がいる枡です。②では i だけ、③では j だけに ▲ を出しています ── その段でもう一方は止まったままなので、印を省きました。琥珀の枠は、その枡の値をいま読んでいるところです。
① はじめ ── pivot を決めて、i と j を両端に置く
pivot ← data[(first ＋ last) ÷ 2 の商] i ← first j ← last
data
12▲
21
33
45
54▲
変数
pivot3
i1
j5
(first ＋ last) ÷ 2 の商 は (1 ＋ 5) ÷ 2 の商 ＝ 3。だから pivot は data[3] ＝ 3 です。i は first の 1番から、j は last の 5番から始まります（この段は、pivot・i・j を決める3行ぶんをまとめて置いています）。
② i を進める ── data[i] ＜ 3 のあいだ、1つずつ右へ
while (data[i] ＜ pivot)
i ← i ＋ 1
endwhile
i ＝ 1
12▲
21
33
45
54
i ＝ 2
12
21▲
33
45
54
i ＝ 3
12
21
33▲
45
54
data[1] ＝ 2 は 3 より小さい → 進む。data[2] ＝ 1 も小さい → 進む。data[3] ＝ 3 は 3 より小さくないので、条件式が偽になりここで抜けます。i は 3。
③ j を戻す ── 3 ＜ data[j] のあいだ、1つずつ左へ
while (pivot ＜ data[j])
j ← j － 1
endwhile
j ＝ 5
12
21
33
45
54▲
j ＝ 4
12
21
33
45▲
54
j ＝ 3
12
21
33▲
45
54
data[5] ＝ 4 は 3 より大きい → 戻る。data[4] ＝ 5 も大きい → 戻る。data[3] ＝ 3 は 3 より大きくないので、ここで抜けます。j は 3 ── ②で止まった i と同じ枡で重なりました。
④ 出会った ── i ≧ j なので繰返しを終了し、α の行へ
if (i ≧ j)
繰返し処理を終了する
endif
data[i]とdata[j]の値を入れ替える
i ← i ＋ 1
j ← j － 1
endwhile
dataの全要素の値を要素番号の順に空白区切りで出力する /*** α ***/
data
12
21
33▲
45
54
変数
pivot3
i3
j3
i も j も 3番。3 ≧ 3 は真なので、すぐ下の 繰返し処理を終了する が実行されます。このとき内側の2つの while はすでに抜けているので、いま入っている繰返しは while (true) だけ ── その endwhile の次、太字の α の行へ進みます。あいだの3行（入れ替える・i を進める・j を戻す）は通りません。α の行は data をそのまま並べて出力する行で、data は {2, 1, 3, 5, 4} のままなので、出力は 2 1 3 5 4 です。
動いたのは i と j だけ。配列 data は {2, 1, 3, 5, 4} のまま ── α の行が出力するのは 2 1 3 5 4 です。
data に書き込む行は、このプログラム全体で data[i]とdata[j]の値を入れ替える の1行だけです。2つの while は i と j を動かすだけなので、その1行を通らないかぎり data は変わりません。④で見たとおり、その行に来ないまま α の行に着くので、出力は data の初期値をそのまま並べた 2 1 3 5 4 です。
答え合わせ ── 動かすと 2 1 3 5 4 が出る
「次へ」で1行ずつ進めてください。i と j の欄と、いま計算していることを見ていくと、上の図と同じ道になります。
1行ずつ追う sort(1, 5) を呼び出してから α の行まで
出典：令和5年度 科目B 公開問題 問3
ループ開始前
配列 data
いま計算していること
変数の状態
α の行が出力したもの
トレース表（進めると1行ずつ積み上がります）
正解は エ
出力は 2 1 3 5 4。1回目の while (true) では、i が 3 まで進み、j が 3 まで戻り、入れ替えを1度もしないまま α の行に着きます。解答群でこの並びは エ だけです。
消えた3つは、どこから来た並びか
α の行は、このあと sort が呼ばれるたびに、もう2回実行されます（ここは解くのに追う必要はありません。呼び出しの重なりそのものは、下の A6 で扱います）。2回目の出力が イ（1 2 3 5 4）、3回目の出力が ア（1 2 3 4 5 ＝ 並べ終わった形）です。「最初に」を読み落とすと、この2つのどちらかを選ぶことになります。ウ（2 1 3 4 5）だけは、α が1度も出力しない並びです。
次に読む
この問題でどこに手間取ったかで、行き先が変わります。
i と j がどこで止まるのかを追いきれなかった人へG10大域変数と局所変数 ── data がどこから見えているのか分からなかった人へA6分割して並べる ── この sort が何をしている手続なのか知りたい人へ一覧科目B 全44問の解説 ── 同じ形の問題を続けて解きたい人へこの記事で引用した資料
いずれも独立行政法人情報処理推進機構（IPA）が公表したものです。IPAは公表済みの試験問題について、教育目的での使用に許諾および使用料を不要としていますが、著作権は放棄していません。本記事では問題文を改変せずに引用しています。
