応用情報技術者試験令和3年秋午前問5 解説付き過去問

問題

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

ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し、更に間隔を詰めて同様の操作を行い、間隔が1になるまでこれを繰り返す。

中間的な基準値を決めて、それよりも大きな値を集めた区分と、小さな値を集めた区分に要素を振り分ける。次に、それぞれの区分の中で同様の操作を繰り返す。

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

未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、未整列の部分を縮めていく。

バブルソートとは、隣り合った要素同士を比較して順序が逆の場合にそれらを入れ替えるという操作を繰り返し、最終的に整列を完成させるアルゴリズムである。

各選択肢の整列方法を具体的に確認し、バブルソートの特徴と比較する。

ある間隔おきに取り出した要素を部分列として整列する方法
これはシェルソートと呼ばれる方法である。シェルソートは、間隔を徐々に狭めていき、最終的に間隔が1になるまで整列処理を行うため、バブルソートとは異なる。
中間的な基準値を決めて、大きい値と小さい値に区分して整列する方法
これはクイックソートと呼ばれる方法である。基準値（ピボット）を選び、それを境界として要素を振り分けるため、バブルソートとは異なる。
隣り合った要素同士を比較し、大小関係が逆であれば入れ替える方法
これはバブルソートそのものである。バブルソートの特徴は「隣り合った要素を比較して順番を入れ替える」という操作を繰り返す点であり、まさにこの記述と一致する。
未整列部分を順序木にして最小値を順に取り出す方法
これはヒープソートと呼ばれる方法である。順序木（ヒープ）を使って最小値（または最大値）を取り出して並べていくものであり、バブルソートとは異なる。

以上の比較から、バブルソートの特徴に当てはまる記述は「隣り合う要素を比較して、大小の順が逆であれば、それらの要素を入れ替えるという操作を繰り返す。」である。

したがって、これが正解となる。