擬似言語のバブルソート、二重ループの動きをトレースで確かめる
ITパスポート試験 令和5年度 問60 ／ アルゴリズムとプログラミング › アルゴリズムとプログラミング
過去問にチャレンジ
手続printArrayは，配列integerArrayの要素を並べ替えて出力する。手続printArrayを呼び出したときの出力はどれか。ここで，配列の要素番号は1から始まる。 〔プログラム〕
○printArray()
整数型：n，m
整数型の配列：integerArray ← {2, 4, 1, 3}
for (nを1から(integerArrayの要素数－1)まで1ずつ増やす)
for (mを1から(integerArrayの要素数－n)まで1ずつ増やす)
if (integerArray[m] > integerArray[m＋1])
integerArray[m]とintegerArray[m＋1]の値を入れ替える
endif
endfor
endfor
integerArrayの全ての要素を先頭から順にコンマ区切りで出力する
- ア
1，2，3，4
- イ
1，3，2，4
- ウ
3，1，4，2
- エ
4，3，2，1
会話形式の解説
講師今回は擬似言語のプログラムを追って、配列がどう並び替わるかを答える問題です。注目してほしいのは、if文で何と何を比べているかと、2つのforの範囲です。
受験者隣り合う要素を比べて、左が大きいときに入れ替えています。これは「バブルソート」でしょうか。
講師そのとおりです。バブルソートは隣接交換法ともいい、隣同士を比べて入れ替えることを繰り返す並べ替えの方法です。「左が右より大きいときに交換」なので、大きい値が右へ移っていきます。
受験者大きい値が右に行くなら、結果は小さい順、つまり昇順になりそうです。ただ、本当にそうなるか自信がないので、手で追ってみたいです。
講師よい考えです。要素数は4なので、外側のnは1から3まで、内側のmは1から「4−n」までです。配列の要素番号は1から始まる指定なので、mが1なら1番目と2番目を比べます。まずn=1から追ってみましょう。
受験者最初は{2, 4, 1, 3}です。m=1で2と4を比べて交換なし。m=2で4と1を交換して{2, 1, 4, 3}。m=3で4と3を交換して{2, 1, 3, 4}です。
講師正確です。外側のループを1回終えると、いちばん大きい4が右端に確定しました。だからn=2では内側の範囲が1つ狭くなり、mは1から2までです。
受験者n=2では、m=1で2と1を交換して{1, 2, 3, 4}。m=2で2と3を比べますが、左が小さいので交換しません。n=3のm=1でも1と2は交換なしなので、出力は「1, 2, 3, 4」ですね。
講師はい、それが正解です。比較は3＋2＋1で6回でした。では「1, 3, 2, 4」はどうでしょう。
受験者いま追った手順では、2と3の並びが入れ替わる場面はありませんでした。n=2のm=2で2と3を比べて交換せず、そのまま{1, 2, 3, 4}になったので、3が2より前に来ることはないと思います。
講師そのとおりです。「3, 1, 4, 2」も、トレースの途中にすら一度も出てこない並びです。隣同士を比べて大きい方を右へ送る規則では、こうはなりません。
受験者「4, 3, 2, 1」は降順なので、条件の向きが逆なら出てくる答えということですね。「左＞右で交換」なら昇順、「左＜右で交換」なら降順と覚えます。
講師その整理で大丈夫です。もう1点、今回はn=2の途中で並べ替えが済んでいますが、プログラムは最後まで比較を続けます。答えるのはあくまで最終状態です。トレース問題では、ループ変数と配列の状態を1行ずつ書き出すと取り違えを防げます。
まとめ
この問題は、隣り合う要素を比べて「左が右より大きければ交換」する二重ループ、つまりバブルソートで配列{2, 4, 1, 3}を並べ替えた結果を問うものです。外側のループを1回終えるごとに未整列部分の最大値が右端に確定するので、内側のループの範囲は1つずつ狭くなります。手で追うと、外側の2回目の途中で{1, 2, 3, 4}になり、その後の比較では交換が起きないため、出力は1, 2, 3, 4です。「左＞右で交換」なら昇順、「左＜右で交換」なら降順になる点と、配列の要素番号が1から始まる指定を押さえておきましょう。
解答・解説
正解はアです
この問題のテーマ
擬似言語で書かれた二重ループのプログラムをトレースして、バブルソート（隣接交換法）で配列{2, 4, 1, 3}を並べ替えた結果を求める問題です。
解き方の考え方
まずプログラムの形を見ます。隣り合う要素を比べ、左が右より大きいときに入れ替えているので、バブルソートで昇順に並べるものだとわかります。要素数は4なので、外側のnは1〜3、内側のmは1〜(4−n)まで回ります。各回で配列がどう変わるかを書き出しながら追うと、確実に答えを確かめられます。比較の回数は3＋2＋1＝6回です。
選択肢ごとの解説
- ○ア 1，2，3，41,2,3,4は、トレースの最終結果と一致します。n=1では、m=1で2と4を比べて交換なし、m=2で4と1を交換して{2,1,4,3}、m=3で4と3を交換して{2,1,3,4}になります。n=2では、m=1で2と1を交換して{1,2,3,4}になり、m=2の2と3は交換しません。n=3のm=1でも1と2は交換しないので、出力は1,2,3,4です。
- ×イ 1，3，2，41,3,2,4は2と3の順序が逆で、昇順になっていません。このプログラムは比較と交換を最後まで行うので、最終的には2と3も昇順に並びます。トレースの結果とも一致しません。
- ×ウ 3，1，4，23,1,4,2は、トレースの途中にも一度も現れない並びです。隣同士を比べて大きい方を右へ送るという規則に従えば、この並びにはなりません。
- ×エ 4，3，2，14,3,2,1は降順の並びです。このプログラムは「左が右より大きいときに交換する」条件なので、大きい値が右へ移動し、結果は昇順になります。降順になるのは、比較の向きが逆の場合です。
補足
今回の配列は外側のループ2回目の途中で整列が終わっていますが、プログラムは最後まで比較を続けます。途中で整列が完了しても、出力は最終状態で答えることに注意しましょう。また、配列の要素番号が1から始まるという指定を見落とすと、ループの範囲を読み違えやすくなります。
POINT
- 隣り合う要素を比べて入れ替える二重ループは、バブルソートの典型的な形です。
- 条件が「左＞右なら交換」なら昇順、「左＜右なら交換」なら降順に並びます。
- 外側のループを1回終えるたびに、未整列部分の最大値が右端に確定するので、内側のループの範囲が1つずつ狭くなります。
- トレース問題では、ループ変数と配列の状態を1行ずつ書き出して追うと、取り違えを防げます。