情報処理安全確保支援士試験 情報処理安全確保支援士試験 令和3年度秋期 午前Ⅰ 問3: バブルソートの説明として，適切なものはどれか。

問題本文

バブルソートの説明として，適切なものはどれか。

選択肢

• ア.ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が1になるまでこれを繰り返す。
• イ.中間的な基準値を決めて，それよりも大きな値を集めた区分と，小さな値を集めた区分に要素を振り分ける。次に，それぞれの区分の中で同様の操作を繰り返す。
• ウ.隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返す。
• エ.未整列の部分を順序木にし，そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して，未整列の部分を縮めていく。

正解

ウ. 隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返す。

解説

バブルソートは隣り合う要素を比較し、順序が逆なら交換する操作を端から繰り返す整列法。1回の走査で最大(最小)値が端へ移動し、これを繰り返して整列する。選択肢ウがこの動作の説明で正解。計算量はO(n^2)と非効率だがアルゴリズムの基礎理解として重要。

選択肢ごとの解説

• ア.間隔を詰めながら部分列を整列するのはシェルソートの説明で、バブルソートではない。
• イ.基準値で大小に振り分けて再帰するのはクイックソートの説明であり誤り。
• ウ.隣接要素を比較し逆順なら入れ替える操作の繰返しはバブルソートそのもので正解。
• エ.順序木(ヒープ)から最小値を取り出すのはヒープソートの説明で、該当しない。