整列（ソート）とは？

整列（ソート）の意味

データをある基準（数値の大小、五十音順など）に従って並べ替える処理。代表的な方法に「バブルソート」（隣り合う要素を比較して交換を繰り返す）などがある。

整列（ソート）の具体例

バブルソートでは、隣接する2つの値を比較して大小が逆なら入れ替える処理を、端から端まで繰り返す。1回のパスで最大値（または最小値）が端に「泡のように」浮かび上がる。

整列（ソート）は試験でどう引っ掛けられる？

並べ替えるのが整列、目的のデータを見つけるのが探索（サーチ）で、混同しやすい。バブルソートは隣同士を比較して交換、選択ソートは最小値を選んで先頭と入れ替えると、手順の違いで区別する。

整列（ソート）と関連する用語

• 二分探索法

整列（ソート）が出た過去問

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

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

  要点：ヒープソートは順序木から最小値を取り出し続ける

  ヒープソートは、未整列部分を親子の大小関係が保たれた順序木（ヒープ）として構成し、根にある最小値（または最大値）を取り出して整列済み部分へ移す操作を繰り返す。取り出すたびにヒープを再構成するため、計算量は最悪でもO(n log n)に収まる。

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

• 次の手順はシェルソートによる整列を示している。データ列 7, 2, 8, 3, 1, 9, 4, 5, 6 を手順(1)〜(4)に従って整列するとき、手順(3)…

  正解：2

  要点：シェルソートの間隔Hは3分の1ずつ縮み、9件なら3→1→0

  データ数は9なので、まずH=[9÷3]=3で手順(2)を実行する。次に手順(3)でH=[3÷3]=1となり、Hは0でないので手順(2)へ戻って整列する。再び手順(3)でH=[1÷3]=0となり、手順(4)で完了する。したがって手順(3)を実行した回数は2回である。

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

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

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

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

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

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

• アルゴリズム設計としての分割統治法に関する記述として、適切なものはどれか。

  正解：全体を幾つかの小さな問題に分割して、それぞれの小さな問題を独立に処理した結果をつなぎ合わせて、最終的に元の問題を解決する方法である。

  要点：分割統治法は小問題に分けて解き結果を統合する

  分割統治法は、解きにくい大きな問題を同じ構造の小さな部分問題に分割し、それぞれを独立に解いてから結果を統合して元の問題の解を得る手法である。マージソートやクイックソート、二分探索などが代表例で、再帰的に分割していく点が特徴である。

  出典：令和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）