整列アルゴリズムとは？せいれつあるごりずむ
整列アルゴリズムとは、データを一定の順序に並べ替える手法の総称。バブルソート・選択ソート・挿入ソートは平均計算量O(n²)、クイックソート・マージソート・ヒープソートは平均O(n log n)。ほかに、作業領域が要るか（マージソートは要る）、同じ値の元の並び順が保たれるか（安定性）という比較軸がある。
最終更新：2026-10-07
この語が出る過去問を解く →背景
整列はデータ処理の下ごしらえとして繰り返し実行されるため、件数が増えたときの伸び方の違いが処理時間にそのまま効く。n＝100万でn²とn log nでは差が5万倍近くになり、「動くが終わらない」処理が生まれる。この違いを件数の関数として表す道具が計算量（オーダ）で、午前I（科目A-1）では手法とオーダの対応、および最悪計算量が問われる。
具体例
クイックソートはトニー・ホーアが、マージソートはジョン・フォン・ノイマンが考案した。実装では、PythonやJavaの標準ライブラリが挿入ソートとマージソートを組み合わせたTimsortを採用しており、既にほぼ整列済みのデータで速い性質を利用している。1万件を100万件に増やすと、O(n²)は1万倍、O(n log n)は約167倍しか増えない。
試験での引っ掛け
クイックソートは平均O(n log n)だが、ピボットの選び方が悪い（既に整列済みの列で端を選ぶなど）と最悪O(n²)まで落ちる。マージソートは最悪でもO(n log n)だが作業領域を要する。「平均が速い＝最悪も速い」ではない点が問われる。
関連用語
出た過去問
出典：平成31年度 春期 高度試験 午前Ⅰ 問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回である。
出典：令和3年度 秋期 高度試験 午前Ⅰ 問3（IPA）
バブルソートの説明として、適切なものはどれか。
正解：隣り合う要素を比較して、大小の順が逆であれば、それらの要素を入れ替えるという操作を繰り返す。
要点：バブルソートは隣接要素の比較交換を繰り返す整列法
バブルソートは隣接する2要素を順に比較し、大小関係が逆なら交換する操作を繰り返す整列法である。1回の走査で最大値（または最小値）が端へ移動し、これを繰り返して全体を整列させる。比較回数はデータ数nに対しO(n^2)で、単純だが効率は高くない。
出典：令和5年度 秋期 高度試験 午前Ⅰ 問3（IPA）
あるデータ列を整列したら状態0から順に状態1、2、・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。 状態0 3, 5, 9, 6, 1, 2 状態1 …
正解：バブルソート
要点：1走査ごとに最大値が末尾へ移るのはバブルソート
状態0から状態1で、末尾方向にある最大値9が右端へ移動し、状態2ではその次に大きい6が右から2番目へ移動している。このように隣接要素を比較・交換しながら大きい値を末尾に押し出していく動きはバブルソートの特徴である。1回の走査ごとに末尾から順に確定していく点がポイント。
出典：令和5年度 春期 高度試験 午前Ⅰ 問3（IPA）
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。