インサーションソート(インサーションソート)とは | 意味や読み方など丁寧でわかりやすい用語解説

インサーションソート（挿入ソート）とは、データを整列させるためのアルゴリズムの一つである。配列やリストなどのデータ構造において、未整列の部分から要素を一つずつ取り出し、すでに整列済みの部分の適切な位置に挿入していくことで全体を整列させる手法である。この操作は、トランプのカードを配られた際に手札を並べ替える動作に似ているとよく例えられるが、ここでは概念的なプロセスに焦点を当てて説明する。

インサーションソートは、非常に直感的で理解しやすいアルゴリズムであり、実装も比較的容易である。対象とするデータセットを、左側がすでに整列済みの部分、右側がまだ整列されていない未整列の部分として概念的に分割し、この境界を一つずつ右に移動させながら処理を進めていく。

アルゴリズムの具体的な手順は以下のようになる。まず、処理対象となるデータ列の最初の要素は、それ単独で既に整列済みであるとみなす。これは、要素が一つしかない列は必ず整列済みであるという考えに基づく。次に、未整列部分の先頭にある要素を取り出す。これを「現在の要素」と呼ぶ。この現在の要素を、整列済み部分の要素と比較しながら適切な挿入位置を探す。比較は通常、整列済み部分の最も右の要素から左方向へ順に行われる。現在の要素が比較対象の要素よりも小さい場合、比較対象の要素を右に一つずらす。この「要素をずらす」操作を、現在の要素よりも小さい要素が見つかるか、または整列済み部分の先頭まで到達するまで繰り返す。適切な挿入位置が見つかったら、そこに現在の要素を挿入する。この一連のプロセスを、未整列部分から取り出す要素がなくなるまで繰り返すことで、データ列全体が整列される。

例えば、[5, 2, 8, 1, 9]という整数列を昇順にソートする例を考える。

1. 最初の要素である5は、それ単独で整列済みとみなす。現在の状態は [5 | 2, 8, 1, 9] となる（縦棒の左側が整列済み、右側が未整列）。
2. 未整列部分の先頭要素である2を取り出す。整列済み部分の要素5と比較する。2は5より小さいため、5を右に一つずらす。挿入位置が見つかったので、2を挿入する。現在の状態は [2, 5 | 8, 1, 9] となる。
3. 未整列部分の先頭要素である8を取り出す。整列済み部分の要素5と比較する。8は5より大きいため、そのままの位置が適切と判断し、挿入する。現在の状態は [2, 5, 8 | 1, 9] となる。
4. 未整列部分の先頭要素である1を取り出す。整列済み部分の要素8と比較する。1は8より小さいため、8を右にずらす。次に5と比較する。1は5より小さいため、5を右にずらす。次に2と比較する。1は2より小さいため、2を右にずらす。先頭まで到達し、挿入位置が見つかったので、1を挿入する。現在の状態は [1, 2, 5, 8 | 9] となる。
5. 未整列部分の先頭要素である9を取り出す。整列済み部分の要素8と比較する。9は8より大きいため、そのままの位置が適切と判断し、挿入する。現在の状態は [1, 2, 5, 8, 9 |] となる。 これで未整列部分がなくなり、データ列全体が昇順に整列された。

インサーションソートの性能について、その計算量はデータがどのような状態にあるかによって変動する。要素数がnである場合、最悪のケースはデータが完全に逆順に並んでいる場合で、このとき各要素を挿入するたびに整列済み部分のすべての要素を比較し、ずらす必要が生じるため、計算量はO(n^2)となる。平均的なケースでも、計算量はO(n^2)である。しかし、最良のケース、つまりデータが既に完全に整列されている場合は、各要素を挿入する際に比較は行われるものの、要素をずらす操作はほとんど発生しないため、計算量はO(n)となる。これは、他のO(n^2)のソートアルゴリズム（例えばバブルソートやセレクションソート）には見られない特徴であり、ほぼ整列済みのデータに対してはインサーションソートが非常に効率的であることを意味する。

インサーションソートは「安定ソート」であるという重要な特性を持つ。安定ソートとは、ソート対象のデータ内に同じ値を持つ要素が複数存在する場合でも、それらの要素の元の相対的な順序がソート後も保たれることを指す。インサーションソートでは、現在の要素を挿入する際に、等しい値の要素を見つけた場合、その要素の「右側」に挿入することで安定性が保たれる。これにより、例えば名前と年齢で構成されるデータにおいて、年齢でソートした後も同じ年齢の人の名前の順序が変更されないといったメリットがある。

また、インサーションソートは「内部ソート」の一種でもある。内部ソートとは、ソートの途中で補助的な記憶領域をほとんど必要とせず、元のデータを格納しているメモリ内で直接ソートを行うアルゴリズムを指す。インサーションソートが必要とする追加のメモリは、現在の要素を一時的に保持するための一時変数程度であり、これはO(1)の空間計算量として表現される。このため、メモリ資源が限られている環境や、非常に大きなデータを扱うが補助記憶領域を確保できない場合に有利な選択肢となり得る。

大規模なデータセットに対しては、クイックソートやマージソートといったO(n log n)のより高速なアルゴリズムが一般的に用いられるが、インサーションソートは小規模なデータセット（一般的に数十から数百要素程度）のソートにおいては、O(n^2)のオーバーヘッドが無視できるほど小さく、実装がシンプルであること、そして特にデータがほぼ整列済みである場合に高いパフォーマンスを発揮するという利点から、依然として有効な選択肢である。実際のシステム開発では、他のより高速なソートアルゴリズムの内部で、処理の最後に残る小さなチャンク（塊）のソートにインサーションソートが使われるケースもある。これは「ハイブリッドソート」と呼ばれる手法の一つであり、インサーションソートの持つ特定の条件下での効率性を活用したものである。このように、インサーションソートは単純ながらも実用的な場面を持つ基礎的なソートアルゴリズムとして、コンピュータサイエンスの分野で広く理解されている。