情報36【電験3種 機械】n個の配列を降順に並べ替えるフローチャートと交換回数！令和2年度 B問題18 完全解説

今回は令和2年度 機械科目 B問題18を解説します。情報35（平成20年度B問題18）の図2と同一テーマ（配列降順ソート）の別年度・別記法版です。n個の配列a[n]を大きい順に並べ替えるフローチャートの空欄(ア)〜(ウ)を求める(a)と、n=5，a=[3,1,2,5,4]としたときに交換処理Xが何回行われるかを求める(b)の問題です。

(a)は判定条件と、退避用変数mを使った値交換の2ステップを穴埋めします。(b)は実際に5個の値を1回ずつ交換しながらトレースし、交換が発生した回数を数えるのが確実な方法です。

令和2年度 機械科目 B問題18：問題文と選択肢

まずは、実際の試験問題を確認してみましょう。

電験3種 機械科目 【情報】 令和2年度 B問題18

　図は，n個の配列の数値を大きい順（降順）に並べ替えるプログラムのフローチャートである。次の(a)及び(b)の問に答えよ。

(a) 図中の(ア)〜(ウ)に当てはまる処理の組合せとして，正しいものを次の(1)〜(5)のうちから一つ選べ。

(b) このプログラム実行時の読込み処理において，n=5とし，a[1]=3，a[2]=1，a[3]=2，a[4]=5，a[5]=4とする。フローチャート中のXで示される部分の処理は何回行われるか，正しいものを次の(1)〜(5)のうちから一つ選べ。

	（ア）	（イ）	（ウ）
(1)	a[i]>a[j]	a[j]←a[i]	a[i]←m
(2)	a[i]>a[j]	a[i]←a[j]	a[j]←m
(3)	a[i]<a[j]	a[j]←a[i]	a[i]←m
(4)	a[i]<a[j]	a[j]←a[i]	a[j]←m
(5)	a[i]<a[j]	a[i]←a[j]	a[j]←m

（1）3　（2）5　（3）7　（4）8　（5）10〔回〕

出題のポイント：降順なら小さい左要素を交換する

降順に並べるので、左側のa[i]が右側のa[j]より小さい、すなわちa[i]＜a[j]のときに交換します。交換はmへa[i]を退避し、a[i]へa[j]、a[j]へmの順に代入します。(b)では比較回数ではなく、この交換処理Xを通った回数だけを数えます。

ポイント解説：比較条件と交換回数を二重ループで追う

本問は情報35の図2と同一テーマ（配列降順ソート）の別年度・別記法版です。(a)は選択ソート的な二重ループの判定・交換ステップの穴埋め、(b)は実際に5個の値を交換しながら回数を数える計算問題です。

退避用変数mを使った値交換「m←a[i]」「a[i]←a[j]」「a[j]←m」という3ステップの構造を理解した上で、(b)では実際の数値を1回ずつ丁寧にトレースします。

問題の解説：7回の交換で降順を完成させる

STEP1　(a) 交換条件（ア）を求める

降順に並べたいので，a[i]がa[j]より小さければ（順序が逆なら）交換が必要。判定（ア）はa[i]<a[j]。

STEP2　(a) 交換処理（イ）（ウ）を求める

m←a[i]（退避）→（イ）a[i]←a[j]（a[j]の値をa[i]へ）→（ウ）a[j]←m（退避していた元のa[i]をa[j]へ）。

以上より（ア）a[i]<a[j]（イ）a[i]←a[j]（ウ）a[j]←mの組合せである(5)が(a)の正解です。

STEP3　(b) 初期配列を1つずつトレースする（前半）

初期配列 a=[3,1,2,5,4]。

[3,1,2,5,4]→(3と5を比較・入替え)①→[5,1,2,3,4]→(1と2を比較・入替え)②→[5,2,1,3,4]→(2と3を比較・入替え)③→[5,3,1,2,4]

STEP4　(b) 続きをトレースし交換回数をまとめる

[5,3,1,2,4]→(3と4を比較・入替え)④→[5,4,1,2,3]→(1と2を比較・入替え)⑤→[5,4,2,1,3]→(2と3を比較・入替え)⑥→[5,4,3,1,2]→(1と2を比較・入替え)⑦→[5,4,3,2,1]

交換（X処理）が発生した回数は合計7回。

以上より(b)の答えは選択肢(3)です。

答え：(a)-(5)，(b)-(3)

まとめ

(a)(ア)	a[i]<a[j]
(a)(イ)	a[i]←a[j]
(a)(ウ)	a[j]←m
初期配列	[3,1,2,5,4]
(b) 交換回数	7回
答え	(a)-(5)，(b)-(3)

▼あわせて解きたい関連問題
・30件の使用電力量データの最大値・平均値算出と降順ソート（平成20年度）：【機械】平成20年度B問題18
・JK-FF3段の非同期式カウンタ回路とタイムチャート：【機械】平成26年度B問題18