情報33【電験3種 機械】配列を使った単純交換法のアルゴリズム（フローチャート）！平成29年度 B問題18 完全解説

今回は平成29年度 機械科目 B問題18を解説します。配列a[1]〜a[5]を比較・交換しながら並べ替える単純交換法（交換ソート）型アルゴリズムのフローチャートについて、出力されるa[5]の値を求める(a)と、フローチャート中のXで示される交換処理が何回行われるかを求める(b)の問題です。

n=5，a[1]=2，a[2]=3，a[3]=8，a[4]=6，a[5]=5という初期値から、二重ループでa[i]とa[j]を比較・交換する様子を1回ずつ丁寧にトレースするのが確実な解き方です。なお原著の選択肢印刷には(a)の2番目のラベルが誤植されている箇所がありますが、本記事では(1)〜(5)の正しい連番に修正して掲載しています。

平成29年度 機械科目 B問題18：問題文と選択肢

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

電験3種 機械科目 【情報】 平成29年度 B問題18

　図のフローチャートで表されるアルゴリズムについて，次の(a)及び(b)の問に答えよ。変数は全て整数型とする。このアルゴリズム実行時の読込み処理において，n=5とし，a[1]=2，a[2]=3，a[3]=8，a[4]=6，a[5]=5とする。

(a) 図のフローチャートで表されるアルゴリズムの機能を考えて，出力されるa[5]の値を求めよ。その値として正しいものを次の(1)〜(5)のうちから一つ選べ。

(b) フローチャート中のXで示される部分の処理は何回行われるか，正しいものを次の(1)〜(5)のうちから一つ選べ。

（1）2　（2）3　（3）5　（4）6　（5）8

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

出題のポイント：単純交換法を正しく追う

このフローチャートは、a[i]をa[i+1]以降の全要素と比較し、a[i]＞a[j]のときだけXの交換処理を行う単純交換法です。比較は合計10回ですが、Xが実行されるのは3回だけです。隣接要素だけを交換するバブルソートとは処理が異なる点にも注意します。

ポイント解説：比較10回のうち交換は3回

本問のフローチャートは配列a[1]〜a[n]を比較・交換しながら並べ替える単純交換法（交換ソート）型アルゴリズムです。外側ループiと内側ループjの二重ループで、a[i]＞a[j]のとき値を交換する処理（X部分）を繰り返します。

(a)はアルゴリズムの機能（昇順に並べ替える）を理解すれば最大値がa[5]に来ることがわかります。(b)は実際に交換が起きた回数を1つずつ数える必要があります。

問題の解説：全10比較を省略せずトレース

STEP1　(a) アルゴリズムの機能を確認する

フローチャートはa[i]とa[j]（j＞i）を比較し，a[i]＞a[j]なら入れ替える処理を全ペアについて繰り返す，単純交換法（交換ソート）による昇順整列です。隣接要素だけを比較するバブルソートとは処理が異なります。

初期値a=[2,3,8,6,5]を昇順に並べ替えると[2,3,5,6,8]となるため，最後の要素a[5]は最大値の8になります（選択肢(5)）。

STEP2　(b) i=1，i=2のときの比較・交換をトレースする

①a[1]=2とa[2]〜a[5]を比較：a[1]が最小のため交換なし。

②a[2]=3とa[3]〜a[5]を比較：a[2]が最小のため交換なし。

STEP3　(b) i=3のときの比較・交換をトレースする

③a[3]=8とa[4]=6を比較：8＞6なので交換 → a=[2,3,6,8,5]（1回目の交換）

④a[3]=6（更新後）とa[5]=5を比較：6＞5なので交換 → a=[2,3,5,8,6]（2回目の交換）

STEP4　(b) i=4のときの比較・交換をトレースし回数をまとめる

⑤a[4]=8とa[5]=6を比較：8＞6なので交換 → a=[2,3,5,6,8]（3回目の交換）

以上，X部分（交換処理）が実行されたのは合計3回（選択肢(1)）。

以上より(a)-(5)，(b)-(1)が正解です。

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

まとめ

初期値a	[2,3,8,6,5]
(a) a[5]	8
(b) 交換回数	3回
答え	(a)-(5)，(b)-(1)

▼あわせて解きたい関連問題
・フローチャート（JIS記号）のループ処理をトレース：【機械】令和5年度上期A問題14
・30件の使用電力量データの最大値・平均値算出と降順ソート：【機械】令和4年度下期B問題18