令和5年度秋期 情報処理安全確保支援士 午前Ⅰ 問3

午前I 問03：大きい数が右へぷくぷく上がるバブルソートを見抜こう

配列の変化を見ると、大きい要素が隣同士の比較で少しずつ右端へ押し出されているよ。水の中の泡が上に上がるみたいに、各パスごとにその中で一番大きい要素が末尾に確定していくので、これはバブルソートの特徴と一致するんだ。

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

整列途中の配列がどう変わっているかを見て、「どの並べ替えアルゴリズムの動きかな？」と判定できるかがポイントだよ。

Bubble Sort Trace

largest element moves to the end in each pass

state0 -> state1: 9 moved rightmost\nstate1 -> state2: 6 moved next

確認ポイント

• 挿入ソートは左側が順に整列済みになる。
• 各回で最大要素が右端へ確定する。
• 隣接交換の動きを見る。

正解

ウ

出典

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

選択肢ア

クイックソートは不正解だよ。クイックソートは、代表になる数を1つ決めて、それより小さい組と大きい組に分ける方法なんだ。受付で「この番号より小さい人はこちら、大きい人はこちら」と分ける感じだね。今回の動きはグループ分けではなく、隣同士の交換で大きい数を右へ送っているので違うよ。

選択肢イ

挿入ソートは不正解だよ。挿入ソートは、手札を1枚ずつ正しい位置に差し込んで並べるような方法なんだ。左側に整列済みの部分を作って、そこへ新しい値を入れていく動きになるよ。今回のように大きい数が右端へ順に流れていく動きではないので違うよ。

選択肢ウ（正解）

バブルソートが正解だよ。隣同士を見比べて、順番が逆なら入れ替える作業をくり返す方法なんだ。満員電車で大きな荷物が少しずつ端へ押し出されるみたいに、今回も大きい数が右端へ1つずつ確定しているから、バブルソートの動きだよ。

選択肢エ

ヒープソートは不正解だよ。これはデータをいったん「親子関係のある木」の形にして、根っこから最大値や最小値を取り出していく方法なんだ。今回の並び替えは、9、6のような大きい数が右端へ順番に押し出されている動きで、木を作って取り出す感じではないよ。