バブルソートとは？

バブルソートの意味

隣り合う2つの要素を比較し、順序が逆なら交換する操作を端から端まで繰り返して整列する方法。1回の走査で最大（または最小）の要素が必ず端へ確定する。実装は単純だが比較回数は要素数nに対しn(n-1)/2回でO(n²)となり、FEでは比較回数・交換回数を数える問題が定番。

バブルソートの具体例

[5,3,4,1]を昇順にすると、1回目の走査で5が右端へ移って[3,4,1,5]、2回目で[3,1,4,5]、3回目で[1,3,4,5]。要素数4なら比較は3+2+1=6回。1回の走査で交換が1度も起きなければ既に整列済みと判断して打ち切る改良版もある。

バブルソートは試験でどう引っ掛けられる？

「隣接交換法」という別名で出題されることがある。比較回数はデータの並びによらずほぼ一定だが、交換回数は並びで変わる点が狙われる。最小値を探して1回だけ交換する選択ソートとの混同にも注意。

バブルソートと関連する用語

• 整列アルゴリズム（バブルソート・選択ソート・挿入ソート）
• 安定ソート

バブルソートが出た過去問

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

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

  要点：バブルソートは隣接要素の比較交換を繰り返す整列法

  バブルソートは隣接する2要素を順に比較し、大小関係が逆なら交換する操作を繰り返す整列法である。1回の走査で最大値（または最小値）が端へ移動し、これを繰り返して全体を整列させる。比較回数はデータ数nに対しO(n^2)で、単純だが効率は高くない。

  出典：令和3年度 秋期 高度共通_午前I試験 am1 問3（IPA）

• あるデータ列を整列したら状態0から順に状態1、2、・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。 状態0 3, 5, 9, 6, 1, 2 状態1 …

  正解：バブルソート

  要点：1走査ごとに最大値が末尾へ移るのはバブルソート

  状態0から状態1で、末尾方向にある最大値9が右端へ移動し、状態2ではその次に大きい6が右から2番目へ移動している。このように隣接要素を比較・交換しながら大きい値を末尾に押し出していく動きはバブルソートの特徴である。1回の走査ごとに末尾から順に確定していく点がポイント。

  出典：令和5年度 秋期 高度共通_午前I試験 am1 問3（IPA）