情報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[1]〜a[n]を比較・交換しながら並べ替えるバブルソート型アルゴリズムです。外側ループiと内側ループjの二重ループで、a[i]＞a[j]のとき値を交換する処理（X部分）を繰り返します。

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

問題の解説

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