整列アルゴリズム（バブルソート・選択ソート・挿入ソート）とは？

整列アルゴリズム（バブルソート・選択ソート・挿入ソート）の意味

単純な整列（ソート）アルゴリズムの代表例。バブルソートは隣接する要素を比較して逆順なら交換する動作を繰り返す、選択ソートは未整列部分から最小（または最大）値を探して先頭と交換する、挿入ソートは整列済み部分に新しい要素を適切な位置へ挿入していく。いずれも計算量はO(n²)。

整列アルゴリズム（バブルソート・選択ソート・挿入ソート）の具体例

[5, 2, 4, 1]をバブルソートで昇順に整列すると、隣接ペアの比較・交換を繰り返しながら大きい値が末尾側へ「浮き上がる」ように移動していく。

整列アルゴリズム（バブルソート・選択ソート・挿入ソート）は試験でどう引っ掛けられる？

3手法とも計算量はO(n²)で大きな差はないが、動作の仕組み（交換の起点、比較対象）を取り違えやすいので、具体的なトレース問題では手順を1ステップずつ丁寧に追う必要がある。

整列アルゴリズム（バブルソート・選択ソート・挿入ソート）と関連する用語

• 計算量とO記法（オーダ記法）

整列アルゴリズム（バブルソート・選択ソート・挿入ソート）が出た過去問

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

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

  要点：ヒープソートは順序木の根から極値を取り出して整列する

  ヒープソートは、未整列部分をヒープ（親子間に大小関係が保たれた順序木）として構成し、根にある最小値または最大値を取り出して整列済み部分へ移す操作を繰り返す方式です。取り出すたびにヒープを再構成するため、計算量は要素数nに対しておおむね n log n となります。他の選択肢はシェルソート、クイックソート、バブルソートの説明です。

  出典：平成28年度 秋期 応用情報技術者試験 午前 問6（IPA）

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

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

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

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

  出典：令和3年度 秋期 応用情報技術者試験 午前 問5（IPA）

• 未整列の配列A[i]（i=1,2,…,n）を、次の流れ図によって整列する。ここで用いられる整列アルゴリズムはどれか。

  正解：バブルソート

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

  内側のループが配列の末尾側から先頭方向へ進みながら、隣り合う要素A[j]とA[j−1]を比較し、逆順なら交換しています。隣接要素の比較交換を繰り返して小さい値を先頭へ押し上げる動きは、バブルソートの典型的な形です。

  出典：令和4年度 秋期 応用情報技術者試験 午前 問6（IPA）

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

  正解：バブルソート

  要点：バブルソートは末尾から大きい値が順に確定していく

  状態0から状態1で最大値9が右端へ、状態1から状態2で次に大きい6が右から2番目へと確定している。これは隣接する2要素を比較・交換しながら末尾へ大きい値を送り出す動きで、バブルソートの典型的な途中経過である。左端の未整列部分がそのまま残っている点も、末尾から確定していく特徴を裏づける。

  出典：令和5年度 秋期 応用情報技術者試験 午前 問6（IPA）

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

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

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

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

  出典：令和6年度 春期 応用情報技術者試験 午前 問7（IPA）