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

選択肢

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

正解と解説

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

バブルソートは隣り合う要素を順に比較し、大小の順序が逆であれば交換する操作を繰り返す整列法である。1回の走査で最大値（または最小値）が端に移動する様子が泡の浮上に似ることから、この名で呼ばれる。実装は単純だが計算量はO(n^2)で、大量データには向かない。

選択肢ごとの解説

• ア一定間隔の部分列を整列しながら間隔を詰めていくのはシェルソートの説明である。
• イ基準値で大小2区分に振り分けて再帰的に処理するのはクイックソートの説明である。
• ウ正しい。隣接要素の比較と交換を繰り返すのがバブルソートである。
• エ未整列部を順序木（ヒープ）にして最小値を取り出すのはヒープソートの説明である。

同じ分野の他の問題

• fact(n)は，非負の整数nに対してnの階乗を返す。fact(n)の再帰的な定義はどれか。2025年度 春期 午前 問7
• 0≦x≦1の範囲で単調に増加する連続関数f(x)がf(0)<0≦f(1)を満たすときに，区間内でf(x)=0であるxの値…2025年度 春期 午前 問2
• 整列方法に関するアルゴリズムの記述のうち、バブルソートの記述はどれか。ここで、整列対象は重複のない1から9の数字がランダ…2024年度 春期 午前 問7
• 正の整数Mに対して、次の二つの流れ図に示すアルゴリズムを実行したとき、結果xの値が等しくなるようにしたい。aに入れる条件…2024年度 春期 午前 問5
• あるデータ列を整列したら状態0から順に状態1、2、・・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。2023年度 秋期 午前 問6