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

午前I 問03：バブルソートの動きを見抜こう

バブルソートは、となり同士の値を見比べて、順番が逆なら入れ替える、という作業を何度もくり返す整列方法だよ。たとえるなら、列に並んだ人をとなり同士で背比べして、背の高い人が少しずつ後ろへ送られていくイメージ。1回の通過ごとに大きい値が末尾側へ移動していくのが特徴だよ。

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

ポイントは、バブルソートの「となり同士を比較して交換する」という特徴を、シェルソート・クイックソート・ヒープソートと区別できるかだよ。分割して考えるクイックソート、間隔をあけて比較するシェルソート、ヒープ構造を使うヒープソートとは動き方が違うことを押さえよう。

Bubble Sort

compare adjacent items and swap if out of order

adjacent compare\nswap repeatedly

確認ポイント

• 間隔を詰める説明はシェルソート寄りです。
• 基準値分割はクイックソートです。
• 隣接交換がキーワードです。

正解

ウ

出典

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

選択肢ア

これは不正解だよ。間隔を空けて取り出したグループを並べ替え、だんだん間隔を詰めるのはシェルソートの説明だよ。まず飛び飛びの席の人を整列させて、最後に隣同士まで細かく整える感じで、バブルソートそのものではないよ。

選択肢イ

これは不正解だよ。中間の基準値を1つ決めて、大きい組と小さい組に分けていくのはクイックソートの考え方なんだ。荷物を「この箱より重いか軽いか」でどんどん分ける感じで、隣同士を入れ替えるバブルソートとは別物だよ。

選択肢ウ（正解）

これは正解だよ。バブルソートは、隣同士を見比べて順番が逆なら入れ替える、という作業を何度も繰り返す方法なんだ。列に並んだ人を、隣の人と背比べして場所を交換していくイメージだよ。

選択肢エ

これは不正解だよ。未整列の部分を順序木にして、そこから最小値などを取り出すのはヒープソートの説明だよ。山積みの荷物を一度取り出しやすい形に積み直して、上から順に持っていく感じで、バブルソートの「隣同士を比べる」やり方ではないよ。