平成25年度秋期 情報処理安全確保支援士 午前Ⅰ 問3

午前I 問03

配列の並び替えは、トランプを順番に整えるイメージで追うとわかりやすいよ。1回のパスでどの位置の値が確定するのかに注目して、配列の変化を一歩ずつ確認しよう。

この問題で問われていること

どの順番で要素が交換されるか、そして各パスが終わった時点で配列のどの範囲がもう動かない状態になるかを追えるかがポイントだよ。

Bubble Sort

bubble sort repeatedly swaps adjacent out-of-order elements so that one extreme value moves to the end each pass

adjacent compare/swap\none value fixed per pass

確認ポイント

• 離れた要素を直接交換しない。
• 1 パスで端が確定する。
• 隣接交換を追う。

正解

ウ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

3は不正解だよ。3回だけだと、例えば21を5・3・17の後ろへ動かす分くらいしか数えられていないよ。実際には53や71も、右側にある3や17より大きいので交換が必要になるんだ。カードの山全体を並べ替えるのに、一部のカードの移動だけ見て終わってしまっている感じだね。

選択肢イ

6は不正解だよ。途中までの交換は数えられているけれど、まだ足りないよ。53と17、71と17のように、右側に小さいカードが残っている組も交換対象になるんだ。隣同士の交換で昇順にするには、最終的に「順番が逆になっている組」を全部直す必要があり、合計は8回だよ。

選択肢ウ（正解）

8が正解だよ。この流れ図は、隣同士を見比べて、左の方が大きければ場所を交換する並べ替えだよ。カードを昇順に並べるときに、前に出すべき小さいカードを少しずつ左へ運ぶ感じだね。交換回数は「左にある大きい数と右にある小さい数の組」の数で、21は5・3・17と3回、5は3と1回、53は3・17と2回、71は3・17と2回、合計8回になるよ。

選択肢エ

15は不正解だよ。15はこの二重ループで隣同士を比較する回数、つまり「何回見比べたか」に近い数だよ。でも問題で聞かれているのは、実際に場所を入れ替えた回数なんだ。窓口で15人を確認しても、席替えが15回起きるとは限らない、というイメージだね。