整列アルゴリズムの計算量とは？せいれつあるごりずむのけいさんりょう
整列アルゴリズムの計算量とは、整列方式を計算量で比較したときの整理。バブル・選択・挿入ソートは平均・最悪ともO(n²)、クイックソート・マージソート・ヒープソートは平均O(n log n)になる。比較に基づく整列はO(n log n)より速くできないことが理論的に示されており、これが実用方式の到達点になっている。
最終更新：2026-10-06
この語が出る過去問を解く →背景
件数が小さいうちはどの方式でも差が出ないが、nが10倍になるとO(n²)は100倍、O(n log n)はおよそ13倍と、伸び方そのものが違う。だから方式の比較は実測秒数ではなく、入力サイズに対する増え方＝オーダーで行う。オーダー記号は定数倍と低次の項を捨てるため、小さいnでは単純な方式のほうが速いという逆転も起きる。応用情報では平均と最悪を区別して選ばせる形で問われる。
具体例
クイックソートはピボットより小さい値と大きい値へ分割することを再帰的に繰り返して平均O(n log n)だが、整列済みのデータに対して端をピボットに取ると分割が偏り最悪O(n²)まで落ちる。マージソートは常にO(n log n)を保証する代わりに、作業用としてO(n)の追加領域を必要とする。
試験での引っ掛け
平均計算量と最悪計算量が一致しない方式がある点を見落とさない（クイックソートが代表例）。またオーダーが同じでも定数倍と追加記憶量は異なり、少件数では挿入ソートのほうが速いことがある。安定性の有無も選択基準で、クイックソートとヒープソートは安定ではない。
関連用語
出た過去問
問題文で直接問われたものと、解説の中で触れられたものが含まれます。
出典：平成28年度 秋期 応用情報技術者試験 午前 問6（IPA）
ヒープソートの説明として、適切なものはどれか。
正解：未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、未整列の部分を縮めていく。
要点：ヒープソートは順序木の根から極値を取り出して整列する
ヒープソートは、未整列部分をヒープ（親子間に大小関係が保たれた順序木）として構成し、根にある最小値または最大値を取り出して整列済み部分へ移す操作を繰り返す方式です。取り出すたびにヒープを再構成するため、計算量は要素数nに対しておおむね n log n となります。他の選択肢はシェルソート、クイックソート、バブルソートの説明です。
出典：令和元年度 秋期 応用情報技術者試験 午前 問8（IPA）
分割統治を利用した整列法はどれか。
正解：クイックソート
要点：クイックソートはピボットで2分割して再帰する分割統治法
分割統治法は、問題を小さな部分問題に分割し、それぞれを解いてから統合する考え方です。クイックソートは基準値（ピボット）で列を2つに分割し、各部分を再帰的に整列するため分割統治に該当します。マージソートも同じく分割統治型です。
出典：令和3年度 秋期 応用情報技術者試験 午前 問5（IPA）
バブルソートの説明として、適切なものはどれか。
正解：隣り合う要素を比較して、大小の順が逆であれば、それらの要素を入れ替えるという操作を繰り返す。
要点：バブルソートは隣接要素の比較交換を繰り返す整列法
バブルソートは隣り合う要素を順に比較し、大小の順序が逆であれば交換する操作を繰り返す整列法である。1回の走査で最大値（または最小値）が端に移動する様子が泡の浮上に似ることから、この名で呼ばれる。実装は単純だが計算量はO(n^2)で、大量データには向かない。
出典：令和3年度 春期 応用情報技術者試験 午前 問7（IPA）解説で登場
アルゴリズム設計としての分割統治法に関する記述として、適切なものはどれか。
正解：全体を幾つかの小さな問題に分割して、それぞれの小さな問題を独立に処理した結果をつなぎ合わせて、最終的に元の問題を解決する方法である。
要点：分割統治法は小問題に分けて解き結果を統合する
分割統治法は、問題を同種の小さな部分問題に分割し、それぞれを独立に（多くは再帰的に）解いてから結果を統合して元の問題の解を得る手法である。マージソートやクイックソート、高速フーリエ変換などが代表例である。
出典：令和4年度 秋期 応用情報技術者試験 午前 問6（IPA）
未整列の配列A[i]（i=1,2,…,n）を、次の流れ図によって整列する。ここで用いられる整列アルゴリズムはどれか。
正解：バブルソート
要点：隣接要素の比較交換を繰り返す整列はバブルソート
内側のループが配列の末尾側から先頭方向へ進みながら、隣り合う要素A[j]とA[j−1]を比較し、逆順なら交換しています。隣接要素の比較交換を繰り返して小さい値を先頭へ押し上げる動きは、バブルソートの典型的な形です。
出典・参考
公式シラバスの1 基礎理論 ＞ 2. アルゴリズム ＞ (2) 代表的なアルゴリズムに掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。