整列（ソート）とは？

整列（ソート）の意味

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

整列（ソート）の具体例

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

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

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

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

• 線形探索法・二分探索法・ハッシュ探索法

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

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

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

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

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

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

• 分割統治を利用した整列法はどれか。

  正解：クイックソート

  要点：クイックソートはピボットで2分割して再帰する分割統治法

  分割統治法は、問題を小さな部分問題に分割し、それぞれを解いてから統合する考え方です。クイックソートは基準値（ピボット）で列を2つに分割し、各部分を再帰的に整列するため分割統治に該当します。マージソートも同じく分割統治型です。

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

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

  正解：2

  要点：シェルソートの間隔Hは3で割り続け、0になるまでの回数を数える

  データ数9なので手順(1)でH=[9÷3]=3となり、手順(2)で間隔3の部分列を整列する。1回目の手順(3)でH=[3÷3]=1、0でないので手順(2)に戻り間隔1で整列する。2回目の手順(3)でH=[1÷3]=0となり手順(4)で完了する。よって手順(3)の実行回数は2回である。

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

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

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

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

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

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

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

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

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

  分割統治法は、問題を同種の小さな部分問題に分割し、それぞれを独立に（多くは再帰的に）解いてから結果を統合して元の問題の解を得る手法である。マージソートやクイックソート、高速フーリエ変換などが代表例である。

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