情報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：問題文と選択肢

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

出典：一般財団法人 電気技術者試験センター「平成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) 機能を見抜けばトレース不要

(a)は「a[5] の値」を問うています——アルゴリズムの機能さえ分かれば、1回もトレースせずに答えが出ます。

a[i]>a[j] のとき交換——左が大きければ入れ替えるのですから、小さい順（昇順）に並べるアルゴリズムです。

判定条件	並ぶ向き	最後の要素
a[i]>a[j] で交換	★昇順（小→大）	最大値
a[i]<a[j] で交換	降順（大→小）	最小値

昇順に並ぶのだから、a[5] には最大値が来ます——初期値 [2, 3, 8, 6, 5] の最大は8。これで(a)は決まりです。

並べ替えの問題では、まず「向き」を確認する——それだけで(a)のような設問は即答できます。浮いた時間を(b)のトレースに使いましょう。

(b) 交換が起きた回数を数える

比較は10回ありますが、実際に交換されるのは3回だけ——初期配列がすでにほぼ整列しているからです。

i	比較	交換	配列
1	2>3 ✕／2>8 ✕／2>6 ✕／2>5 ✕	0回	[2,3,8,6,5]
2	3>8 ✕／3>6 ✕／3>5 ✕	0回	[2,3,8,6,5]
3	8>6 ○／6>5 ○	★2回	[2,3,5,8,6]
4	8>6 ○	★1回	[2,3,5,6,8]

i＝1 と i＝2 では一度も交換が起きません——2 と3 がすでに正しい位置にあるからです。交換は合計3回になります。

i＝3 の2回目に注目してください——比べているのは更新後の a[3]＝6 と a[5]＝5。交換のたびに a[i] が変わるので、元の8 と比べてはいけません。

交換回数は「順序が逆の組」の数に等しい

この形のアルゴリズムには、便利な性質があります——交換回数は、最初の配列で「順序が逆になっている組」の数と一致するのです。

組（i<j）	値	順序
(3, 4)	8 と6	★逆
(3, 5)	8 と5	★逆
(4, 5)	6 と5	★逆
その他7組	—	正しい向き

逆になっている組は3つ——交換回数3回とぴったり一致します。トレースの答え合わせに使えます。

数え方は簡単——各要素について、それより右側にある小さい値の個数を数えて足すだけ。[2,3,8,6,5] なら 0＋0＋2＋1＋0＝3 です。

トレースが長くなる問題ほど、この検算が効きます——2通りの方法で同じ数になれば、まず間違いありません。

同じ単純交換法が令和2年度 B問題18や令和4年度下期 B問題18でも出題されています（令和2年度／令和4年度下期）。

単純交換法とバブルソートの違い

本問は「単純交換法」——よく似たバブルソートとは、比べる相手が違います。

	単純交換法（本問）	バブルソート
比べる相手	★離れた要素も含めて総当たり	★隣どうしだけ
比較回数	n(n−1)/2	n(n−1)/2
交換回数	少ない（逆順の組の数）	多くなりやすい

比較回数は同じですが、1回の交換で運べる距離が違う——単純交換法は離れた位置へ一気に動かせます。

バブルソートは隣どうししか交換しないので、端から端まで動かすには何度も交換が必要——泡が水面へ上っていくような動きから、この名が付きました。

初期配列で交換回数は大きく変わる

初期配列の状態	交換回数
すでに昇順	★0回
本問（[2,3,8,6,5]）	3回
完全な降順	★10回（最大）

本問の初期配列は、前半の2 と3 がすでに正しい位置——だから交換が3回で済みました。「ほぼ整列済みなら交換は少ない」という感覚を持っておくと、答えの妥当性が判断できます。

10 という選択肢は、比較回数であると同時に最大の交換回数——今回の配列でそれはあり得ないと気づけるはずです。

流れ図のトレースを速く正確に

本問のようなトレース問題は、書き方を決めておくと速くなります。

工夫	やり方
配列を1行で書く	[2,3,8,6,5] のように角かっこで
交換したときだけ書き直す	★変化がなければ書かない
交換のたびに番号を振る	①②③…と数えれば数え落とさない
i ごとに区切る	どこまで進んだか見失わない

比較のたびに配列を書き写すと、行数が10行を超えて混乱します——交換が起きたときだけ書くのが要領です。本問なら3行で済みます。

番号を振っておけば、最後に数えるだけ——「何回だったか」を思い出す必要がありません。

時間配分の目安

B問題は(a)(b)で各5点——1問に使えるのは7〜8分です。(a)を機能から即答すれば、(b)に6分以上かけられます。

トレースは急ぐと必ず間違えます——時間を作ってから、ていねいに進める。そのために(a)を素早く片付けるという順序が効いてきます。

まとめ

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

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