A-1アルゴリズム・プログラミング · アルゴリズム

挿入ソート

Insertion Sort

そうにゅうそーと

整列済みの部分に、未整列部分の先頭の要素を適切な位置に挿入する操作を繰り返して整列するアルゴリズム。計算量はO(n²)だが、ほぼ整列済みのデータに対しては高速に動作する。

共有:

他の資格での定義

未整列部分の先頭要素を整列済み部分の適切な位置に挿入する操作を繰り返す整列アルゴリズム。平均・最悪計算量はO(n²)だが、ほぼ整列済みのデータに対してはO(n)で高速。安定ソート。

整列済みの部分に、未整列の部分の先頭の要素を適切な位置へ挿入することを繰り返す整列のアルゴリズム。計算量は平均・最悪でO(n²)だが、ほぼ整列済みのデータではO(n)に近く速い。安定な整列で、要素数の少ない区間の整列としてクイックソートなどと組み合わせて使われる。

Past Exams

過去問で 4 回出題（応用情報技術者試験 3・高度試験午前Ⅰ 1）

出典: 独立行政法人情報処理推進機構（IPA）の過去問題。問題文は IPA のサイトの PDF で確認できます。「選択肢」は、問題文ではなく選択肢に出たものです。用語名で照合しているため、関係の薄い問題が含まれることがあります。

隣り合う要素を比較し、順序が逆なら交換する操作を、列の端から端まで繰り返して整列するアルゴリズム。仕組みは単純だが、計算量はO(n²)で、大量のデータには向かない。

未整列の部分から最小（または最大）の要素を選び、未整列部分の先頭と交換する操作を繰り返して整列するアルゴリズム。交換の回数は少ないが、比較の回数が多く、計算量はO(n²)である。

アルゴリズムの実行に必要な処理の手間（基本操作の回数）を、入力データの大きさnの関数として表したもの。オーダ記法で表し、例えば線形探索はO(n)、2分探索はO(log n)になる。

アルゴリズムの実行に必要な記憶領域（メモリ）の大きさを、入力データの大きさnの関数として表したもの。オーダ記法で表し、作業用の配列を必要とするマージソートはO(n)になる。時間計算量と引換えになることが多い。

基準値（ピボット）を選び、それより小さい要素と大きい要素のグループに分ける操作を、各グループに再帰的に繰り返して整列するアルゴリズム。平均の計算量はO(n log n)で実用上最も速い部類だが、ピボットの選び方が悪いと最悪O(n²)になる。

データを半分ずつに分割していき、整列済みの小さな列どうしを併合（マージ）することを繰り返して整列するアルゴリズム。最悪でも計算量はO(n log n)で安定した整列ができるが、作業用の記憶領域が必要になる。