今回は令和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：問題文と選択肢
まずは、実際の試験問題を確認してみましょう。
出典：一般財団法人 電気技術者試験センター「令和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)は判定条件と交換処理の穴埋め——「どちらに並べたいか」から不等号の向きが決まります。
| 空欄 | 答え | 意味 |
| (ア) | a[i]<a[j] | ★降順なので、左が小さければ交換 |
| (イ) | a[i]←a[j] | 退避の後、右の値を左へ |
| (ウ) | a[j]←m | 退避していた元の左の値を右へ |
降順＝大きい順——左のほうが大きくあるべきです。だから左が小さいときが「順序が逆」——そのとき交換します。
値の交換は3ステップ
| 順 | 処理 | 役割 |
| ① | m←a[i] | ★左の値を退避 |
| ② | a[i]←a[j] | 右の値を左へ（左は上書きされる） |
| ③ | a[j]←m | 退避した値を右へ |
①を飛ばすと元の a[i] が消えてしまいます——「コップの水を入れ替えるには3つめのコップが要る」のと同じ。退避用の変数 m がその3つめです。
(b) 交換が起きた回数を数える
問われているのは「Xを通った回数」＝交換回数——比較回数ではありません。ここが最大の落とし穴です。
| i | j | 比較 | 交換 | 配列 |
| 1 | 2〜5 | 3<1 ✕／3<2 ✕／3<5 ○／5<4 ✕ | 1回 | [5,1,2,3,4] |
| 2 | 3〜5 | 1<2 ○／2<3 ○／3<4 ○ | 3回 | [5,4,1,2,3] |
| 3 | 4〜5 | 1<2 ○／2<3 ○ | 2回 | [5,4,3,1,2] |
| 4 | 5 | 1<2 ○ | 1回 | [5,4,3,2,1] |
交換は 1＋3＋2＋1＝7回——一方、比較は 4＋3＋2＋1＝10回です。選択肢に10 が用意されているのは、この取り違えを狙ったものでしょう。
⚠️ よくある間違い
比較回数10 を答えてしまうのが最大の誤り——選択肢(5)がまさにその10 です。
設問は「Xで示される部分の処理は何回」——X は判定のYES側にある交換処理です。流れ図のどこにX があるかを最初に確認してください。
もう1つの誤りは、トレースを途中で省略すること——「だいたいこうなるはず」で進めると必ずずれます。1行ずつ配列を書き写すのが結局は速いのです。
比較回数と交換回数の関係
比較回数は配列の中身によらず一定——交換回数だけが中身で変わります。
| 配列の状態 | 交換回数 | 理由 |
| すでに降順 | ★0回 | a[i]<a[j] が一度も成立しない |
| 本問（[3,1,2,5,4]） | 7回 | ばらばらの並び |
| 完全な昇順 | 10回（最大） | すべての比較で交換 |
最悪でも比較回数と同じ10回——交換が比較を上回ることはありません。だから7 という答えは10 以下——検算の目安にもなります。
n が30 なら比較は435回——n2 に比例して増えることになります。データが10倍になれば時間は約100倍——これが単純な並べ替えの限界です。
⏱️ 本番での進め方
①(a) 降順なら「左が小さいとき」交換。(ア)はa[i]<a[j]。
②交換は退避→上書き→書き戻しの3ステップ。
③★(b)は交換回数。比較回数10 と混同しない。
④ i ごとに区切って数えると数え落としが防げる。
💡 覚え方
「降順なら左が小さいとき入れ替え」——並べたい向きの逆が交換条件。そして「問われているのは比較か交換か」を設問文で必ず確認してください。
同じ降順ソートが平成20年度 B問題18や平成29年度 B問題18でも出題されています（平成20年度／平成29年度）。
流れ図を読む3つの区画
どんな流れ図も、初期化・繰り返し・後処理の3区画に分けられます——まずこの目で全体を眺めると、構造がつかめます。
| 区画 | 本問での内容 |
| 初期化 | n とa[1]〜a[n] の読み込み |
| 繰り返し | ★二重ループ（i とj）で比較と交換 |
| 後処理 | 並べ替えた配列の出力 |
本問で問われているのは、すべて繰り返しの中身——二重ループの内側にある判定と交換です。そこだけに集中すればよいと分かります。
二重ループの範囲
外側は i＝1 から n−1 まで、内側は j＝i＋1 から n まで——j が i より後ろから始まるのが要点です。
| i | j の範囲 | 比較回数 |
| 1 | 2〜5 | 4回 |
| 2 | 3〜5 | 3回 |
| 3 | 4〜5 | 2回 |
| 4 | 5 | 1回 |
同じ組を2度比べないための仕組み——j を i より後ろに限ることで、すべての組を1回ずつ調べられます。
合計は 4＋3＋2＋1＝10回——これが n(n−1)/2 の正体です。1 から n−1 までの和になっています。
この方式は何をしているのか
外側のループが1周終わるたびに、a[i] にはそこから後ろで最大の値が入ります——だから先頭から順に確定していくのです。
| i のループ終了時 | 確定する値 | 本問での値 |
| i＝1 の後 | ★全体の最大値 | a[1]＝5 |
| i＝2 の後 | 2番目に大きい値 | a[2]＝4 |
| i＝3 の後 | 3番目 | a[3]＝3 |
| i＝4 の後 | 4番目と5番目 | a[4]＝2、a[5]＝1 |
「先頭を確定させてから、残りで同じことを繰り返す」——これが選択ソートの考え方です。トレースの途中経過を見れば、左から順に大きい値が並んでいくのが分かります。
この性質を知っていると、途中経過の検算ができます——i＝1 が終わった時点で a[1] が最大値5 になっていなければ、どこかで間違えたということ。長いトレースの途中で確認できるのは大きな利点です。
まとめ
| (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
コメント