整列方法に関するアルゴリズムの記述のうち、バブルソートの記述はどれか。ここで、整列対象は重複のない1から9の数字がランダムに並んでいる数字列とする。

選択肢

• ア数字列の最後の数字から最初の数字に向かって、隣り合う二つの数字を比較して小さい数字が前に来るよう数字を入れ替える操作を繰り返し行う。
• イ数字列の中からランダムに基準となる数を選び、基準より小さい数と大きい数の二つのグループに分け、それぞれのグループ内も同じ操作を繰り返し行う。
• ウ数字列をほぼ同じ長さの二つの数字列のグループに分割していき、分割できなくなった時点から、グループ内で数字が小さい順に並べる操作を繰り返し行う。
• エ未処理の数字列の中から最小値を探索し、未処理の数字列の最初の数字と入れ替える操作を繰り返し行う。

正解と解説

正解：ア 数字列の最後の数字から最初の数字に向かって、隣り合う二つの数字を比較して小さい数字が前に来るよう数字を入れ替える操作を繰り返し行う。

バブルソートは、隣り合う2要素を比較して順序が逆なら交換する操作を、列の端から端まで繰り返す手法である。1回の走査で最も小さい（または大きい）値が端まで移動していく様子から泡に例えられる。隣接要素の比較・交換の繰返しという点が他の整列法との決定的な違いである。

選択肢ごとの解説

• ア正しい。隣り合う二つを比較して入れ替える操作の繰返しという記述が、バブルソートの定義に一致する。
• イ基準値（ピボット）で大小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
• 正の整数Mに対して、次の二つの流れ図に示すアルゴリズムを実行したとき、結果xの値が等しくなるようにしたい。aに入れる条件…2024年度 春期 午前 問5
• あるデータ列を整列したら状態0から順に状態1、2、・・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。2023年度 秋期 午前 問6
• 配列に格納されたデータ2, 3, 5, 4, 1に対して、クイックソートを用いて昇順に並べ替える。2回目の分割が終わった…2023年度 春期 午前 問7