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

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

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

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

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

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

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

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

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

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

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

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

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

  バブルソートは隣接する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）