EN
JP
KRInsertion SortをJavaScriptで実装する方法｜挿入ソートの仕組みと使いどころを解説
Insertion Sortは、ソートアルゴリズムの基本としてよく学ばれる手法の一つです。日本語では挿入ソートと呼ばれ、配列の要素を一つずつ取り出し、すでに並んでいる部分の適切な位置へ挿入していくことで、全体を整列させます。考え方は、人がトランプの手札を並べる動作に似ています。新しいカードを受け取ったとき、すでに並んでいる手札の中で正しい位置を探して差し込むように、Insertion Sortでは未処理の要素をソート済み領域へ挿入していきます。この直感的なイメージがあるため、JavaScriptでアルゴリズムを学ぶ初心者にも理解しやすいソート方法です。
Insertion Sortは、平均ケースや最悪ケースではO(n^2)の時間計算量になります。そのため、大規模でランダムなデータを高速に並び替える用途には向いていません。しかし、すでにほぼ整列されているデータに対しては比較的効率よく動作することがあります。この点は、Bubble SortやSelection Sortと同じ基本ソートに分類されながらも、Insertion Sortならではの特徴です。本記事では、Insertion Sortの仕組み、JavaScriptでの実装方法、処理の流れ、計算量、ほぼ整列済みデータでの強み、実務での位置づけまで、初心者にも分かりやすく解説します。
1. Insertion Sortとは？
Insertion Sortとは、配列の左側をソート済み領域として扱い、右側から要素を一つずつ取り出して、正しい位置に挿入していくソートアルゴリズムです。最初は先頭の1要素だけをソート済みとみなし、2番目の要素を取り出して、左側の正しい位置へ挿入します。次に3番目、4番目と同じように処理を進め、ソート済み領域を少しずつ広げていきます。配列全体を一気に並び替えるのではなく、整列済みの範囲を段階的に拡張していくのが特徴です。
Insertion Sortは、比較と交換を繰り返すBubble Sortや、最小値を探して交換するSelection Sortとは考え方が異なります。Insertion Sortでは、現在の要素を一時的に保持し、左側のソート済み領域の要素を必要に応じて右へずらしながら、挿入すべき位置を作ります。この「ずらして挿入する」という動きは、配列操作を学ぶうえで非常に重要です。JavaScriptで実装すると、インデックスの移動、値の一時保存、whileループによる比較など、配列処理の基礎をまとめて練習できます。
1.1 挿入ソートの基本イメージ
たとえば、[5, 3, 8, 1]という配列を昇順に並べたいとします。まず、先頭の5だけをソート済みと考えます。次に3を取り出し、左側にある5と比較します。3は5より小さいため、5を右へずらし、3を先頭に挿入します。この時点で左側の[3, 5]は整列済みです。次に8を取り出すと、8は5より大きいため、そのまま後ろに置けば問題ありません。最後に1を取り出し、8、5、3を右へずらして、1を先頭に挿入します。
このように、Insertion Sortでは、毎回「取り出した値をソート済み領域の正しい位置へ入れる」ことを繰り返します。重要なのは、挿入対象の値を一時的に保存し、左側の要素を比較しながら必要に応じて右へ移動させる点です。単純に隣同士を交換するのではなく、挿入するための空き位置を作るように処理します。小さな配列でこの流れを手で追うと、Insertion Sortがどのように配列を整列させているのかを理解しやすくなります。
1.2 Insertion Sortの特徴
Insertion Sortの特徴は、すでにほぼ整列されているデータに対して効率よく動作しやすいことです。配列がほとんど正しい順序になっている場合、各要素を挿入するために大きく移動させる必要がありません。そのため、内側のループがあまり実行されず、処理回数が少なくなります。逆に、完全に逆順に近い配列では、多くの要素を右へずらす必要があるため、処理が重くなります。このように、入力データの状態によって性能が変わりやすいのがInsertion Sortの特徴です。
また、Insertion Sortは安定ソートとして実装しやすいアルゴリズムです。安定ソートとは、同じ値を持つ要素の元の順序を保ったまま並び替えるソートのことです。数値配列だけでなく、オブジェクト配列を扱う場合、同じスコアや同じ価格を持つ要素の順序を維持したいことがあります。Insertion Sortでは、比較条件を適切に設定すれば、同じ値の順序を変えずに並び替えることができます。学習用としてだけでなく、ソートの安定性を理解するためにも役立つアルゴリズムです。
1.3 Bubble SortやSelection Sortとの違い
Bubble Sortは、隣り合う要素を比較して順序が逆なら交換するアルゴリズムです。Selection Sortは、未ソート領域から最小値を探して現在位置と交換するアルゴリズムです。一方、Insertion Sortは、現在の要素を取り出して、すでに整列されている領域の正しい位置へ挿入します。つまり、Bubble Sortは隣接交換、Selection Sortは最小値選択、Insertion Sortは挿入位置の探索と要素移動が中心になります。同じ基本ソートでも、データの動き方や考え方は大きく異なります。
Insertion Sortは、ほぼ整列済みのデータに強いという点で、Bubble SortやSelection Sortとは異なる実用的な性質を持っています。Bubble Sortも最適化すれば整列済みデータで早期終了できますが、基本的には隣接交換を繰り返します。Selection Sortはデータが整列済みでも最小値探索を行うため、比較回数が大きく変わりません。Insertion Sortは、すでに正しい順序に近い配列では移動回数が少なく済むため、基本ソートの中でも特徴を比較しやすいアルゴリズムです。
2. Insertion Sortの動作手順
Insertion Sortは、配列の先頭から順番にソート済み領域を広げていくアルゴリズムです。最初の要素は、1つだけならすでに整列されていると考えます。そのため、実際の処理は2番目の要素から始まります。外側のループで挿入対象となる値を選び、内側のループで左側のソート済み領域を右から左へ確認します。挿入対象より大きい値があれば右へずらし、適切な位置が見つかったら、そこに挿入対象の値を入れます。
この処理で重要なのは、挿入対象の値を一時的に保存することです。左側の要素を右へずらしていく途中で、元の位置の値が上書きされる可能性があるため、あらかじめcurrentのような変数に保存しておく必要があります。Insertion Sortは、値を何度も交換するというより、要素を右へ移動させて挿入位置を作るイメージです。この違いを理解すると、コードのwhileループが何をしているのか分かりやすくなります。
2.1 ソート済み領域を作る
Insertion Sortでは、配列の左側をソート済み領域として扱います。最初は先頭の1要素だけがソート済みです。配列の長さが1であれば、それ以上並び替える必要はありません。2番目の要素から順番に取り出し、左側のソート済み領域の中で正しい位置を探します。そして、その位置へ挿入することで、ソート済み領域が一つ広がります。この処理を配列の最後まで繰り返すと、最終的に全体が整列されます。
ソート済み領域を意識すると、Insertion Sortの構造が理解しやすくなります。外側のループのインデックスiは、これから挿入する対象の位置を表します。iより左側はすでに整列済みであり、iの要素をその中へ挿入することで、整列済み領域を拡大します。つまり、Insertion Sortは未ソート領域から一つずつ要素を取り出し、ソート済み領域へ追加していくアルゴリズムです。この視点を持つと、処理の流れを追いやすくなります。
2.2 挿入対象を一時保存する
挿入対象の値は、currentのような変数に一時保存します。たとえば、const current = result[i]のように書くことで、現在挿入しようとしている値を保持します。その後、左側のソート済み領域を右から左へ確認し、currentより大きい値があれば右へずらします。値をずらす処理を行うと、元のresult[i]の位置が上書きされるため、currentに保存しておくことが必要です。
この一時保存の考え方は、Insertion Sortを理解するうえで非常に重要です。もしcurrentを保存せずに要素を右へずらしてしまうと、挿入対象の値が失われる可能性があります。アルゴリズム学習では、変数がどの値を保持しているのかを意識することが大切です。Insertion Sortでは、currentが挿入したい値、jが左側を確認するためのインデックス、result[j + 1]が値を移動させる位置として機能します。
2.3 正しい位置へ挿入する
Insertion Sortでは、左側の要素がcurrentより大きい間、その要素を右へずらします。たとえば、昇順に並べる場合、result[j] > currentであれば、result[j]はcurrentより後ろにあるべき値です。そのため、result[j + 1] = result[j]として一つ右へ移動させます。その後、jを一つ左へ進めて、さらに前の要素と比較します。この処理を繰り返すことで、currentを挿入するための位置が見つかります。
条件を満たさなくなった時点で、currentをresult[j + 1]に代入します。ここが、挿入対象の正しい位置です。jは比較しながら左へ移動しているため、最終的にj + 1が挿入位置になります。この流れは最初少し分かりにくいかもしれませんが、小さな配列でjの値を追うと理解しやすくなります。Insertion Sortでは、要素を右へずらしてから空いた場所に値を入れるという動きを意識することが大切です。
3. JavaScriptでInsertion Sortを実装する
JavaScriptでInsertion Sortを実装するには、外側のforループと内側のwhileループを使います。外側のループは、2番目の要素から最後の要素まで順番に挿入対象を選びます。内側のwhileループは、左側のソート済み領域を右から左へ確認し、挿入対象より大きい値を右へずらします。最後に、空いた位置へ挿入対象の値を入れます。この構造を理解すると、Insertion Sortのコードは比較的読みやすくなります。
元の配列を変更したくない場合は、最初にコピーを作ってから処理するのが安全です。この記事では、const result = [...numbers]として元配列のコピーを作成し、そのコピーに対してソート処理を行います。こうすることで、関数に渡した元の配列を壊さず、ソート済みの新しい配列を返せます。JavaScriptではsort()も元配列を変更するため、アルゴリズムを自作する場合でも、元データを保護する意識を持つことが大切です。
3.1 基本実装
以下は、数値配列を昇順に並べるInsertion Sortの基本実装です。外側のループはi = 1から始まります。これは、先頭の1要素をすでにソート済みとみなすためです。currentには現在挿入したい値を保存し、jにはその左隣のインデックスを設定します。whileループでは、jが0以上で、かつresult[j]がcurrentより大きい間、result[j]を右へずらします。
whileループが終了したら、currentをresult[j + 1]に代入します。これにより、挿入対象の値が正しい位置に入ります。たとえば、[5, 3, 8, 1]の場合、3は5の前に挿入され、8はそのまま残り、1は先頭に挿入されます。このコードは短いですが、ソート済み領域、挿入対象、一時保存、要素移動というInsertion Sortの重要な考え方がすべて含まれています。
function insertionSort(numbers) { const result = [...numbers]; for (let i = 1; i < result.length; i++) { const current = result[i]; let j = i - 1; while (j >= 0 && result[j] > current) { result[j + 1] = result[j]; j--; } result[j + 1] = current; } return result;}console.log(insertionSort([5, 3, 8, 1])); // [1, 3, 5, 8]
3.2 処理の流れを確認する
入力が[5, 3, 8, 1]の場合、最初に処理されるのは3です。5だけがソート済み領域とみなされているため、3を5と比較します。3は5より小さいので、5を右へずらし、3を先頭へ挿入します。次に8を処理します。8は左側の5より大きいため、移動する必要はありません。そのままの位置で、ソート済み領域は[3, 5, 8]になります。最後に1を処理し、8、5、3を右へずらして、1を先頭へ挿入します。
この流れを見ると、Insertion Sortが単純な交換ではなく、要素の移動によって挿入位置を作っていることが分かります。currentは一時的に保持され、左側の要素が右へずれていき、最後に空いた位置へcurrentが入ります。学習時には、各ステップでcurrent、j、配列の状態を紙に書くと理解しやすいです。また、コード内に一時的にconsole.log(result)を入れて確認すると、配列がどのように変化しているかを視覚的に追うことができます。
3.3 降順にする方法
Insertion Sortで降順に並べたい場合は、比較条件を逆にします。昇順では、左側の値がcurrentより大きい場合に右へずらしました。降順では、大きい値を前に置きたいので、左側の値がcurrentより小さい場合に右へずらします。つまり、whileループの条件をresult[j] < currentに変更します。それ以外の構造は昇順の場合とほとんど同じです。
降順のInsertion Sortは、ランキング、スコア一覧、売上金額の高い順、人気数の多い順などを考える練習として役立ちます。比較条件を変えるだけで並び順が変わることを理解すると、JavaScript標準のsort()でa - bとb - aを使い分ける感覚も身につきやすくなります。Insertion Sortを昇順と降順の両方で実装してみると、比較条件がアルゴリズム全体の動きにどのように影響するのかを理解できます。
function insertionSortDesc(numbers) { const result = [...numbers]; for (let i = 1; i < result.length; i++) { const current = result[i]; let j = i - 1; while (j >= 0 && result[j] < current) { result[j + 1] = result[j]; j--; } result[j + 1] = current; } return result;}
4. Insertion Sortの計算量
Insertion Sortの時間計算量は、入力データの状態によって大きく変わります。配列がすでに整列されている場合、ほとんど要素を移動する必要がないため、非常に少ない処理で完了します。一方、配列が完全に逆順になっている場合は、各要素を左側の先頭近くまで挿入する必要があり、多くの比較と移動が発生します。このように、Insertion Sortは最良ケースと最悪ケースの差が分かりやすいアルゴリズムです。
平均ケースや最悪ケースではO(n^2)になるため、大規模なランダムデータには向いていません。しかし、ほぼ整列済みの小さなデータに対しては効率よく動作することがあります。この性質は、基本ソートの中でもInsertion Sortがよく取り上げられる理由の一つです。計算量を学ぶときは、単にO(n^2)と覚えるだけでなく、どのような入力で処理が軽くなり、どのような入力で重くなるのかを考えることが大切です。
4.1 最良ケース
Insertion Sortの最良ケースは、配列がすでに昇順に整列されている場合です。この場合、各要素を確認しても、左側の要素を右へずらす必要がありません。whileループの条件であるresult[j] > currentがすぐに false になるため、内側のループはほとんど実行されません。そのため、外側のループで配列を一度確認するだけに近い処理になり、時間計算量はO(n)になります。
この性質は、Insertion Sortの大きな強みです。Bubble SortやSelection Sortと同じ基本ソートに分類されますが、整列済みデータに対しては非常に効率よく動作します。たとえば、ほとんど並んでいる配列に少数の新しい要素が追加されたような状況では、Insertion Sortの考え方が有効になることがあります。最良ケースを理解すると、なぜInsertion Sortが「ほぼ整列済みデータに強い」と言われるのかが分かります。
4.2 平均ケース
平均ケースは、配列の要素がランダムに並んでいる場合です。この場合、各要素を正しい位置へ挿入するために、ある程度の比較と移動が必要になります。すべての要素が少しずつ移動する可能性があるため、処理回数は増えやすくなります。その結果、平均的な時間計算量はO(n^2)になります。要素数が増えると処理が重くなりやすいため、ランダムな大量データには適していません。
平均ケースを理解することは、Insertion Sortを実務で使うべきかどうか判断するうえで重要です。小さな配列であれば問題なく動作しますが、数千件、数万件のランダムデータをInsertion Sortで処理すると、パフォーマンスに問題が出る可能性があります。実務ではJavaScript標準のsort()を使う方が一般的です。Insertion Sortは、学習用として、またはほぼ整列済みの小さなデータの性質を理解するためのアルゴリズムとして捉えるとよいでしょう。
4.3 最悪ケース
Insertion Sortの最悪ケースは、昇順に並べたい配列が完全に降順になっている場合です。たとえば、[5, 4, 3, 2, 1]のような配列を昇順にする場合、各要素を左側の先頭近くまで移動させる必要があります。4を5の前に挿入し、3を5と4の前に挿入し、2をさらに前へ挿入するというように、多くの要素移動が発生します。そのため、比較回数と移動回数が非常に多くなります。
最悪ケースの時間計算量はO(n^2)です。この点では、Bubble SortやSelection Sortと同じく、大規模データには向いていません。特に逆順に近いデータでは、Insertion Sortの弱点がはっきり出ます。アルゴリズムを学ぶときは、最良ケースだけでなく、最悪ケースも意識することが重要です。同じInsertion Sortでも、入力データの状態によって処理速度が大きく変わることを理解すると、計算量の考え方がより実践的に身につきます。
5. Insertion Sortの使いどころと学習ポイント
Insertion Sortは、実務で大規模データに使うアルゴリズムではありません。しかし、小さな配列や、すでにほぼ整列されているデータに対しては、考え方として有効な場面があります。また、アルゴリズム学習では、ソート済み領域、挿入位置、要素移動、一時保存といった重要な概念をまとめて学べます。Bubble SortやSelection Sortとは異なる視点で配列を並び替えるため、ソートアルゴリズム全体への理解を深めるのに役立ちます。
JavaScriptの学習では、標準のsort()だけを使っていると、配列がどのように並び替えられているのかを意識しないままになりがちです。Insertion Sortを自分で実装してみると、要素の比較や移動、インデックスの管理がどのように行われるのかを具体的に理解できます。実務では標準メソッドを使い、学習ではInsertion Sortを通じてアルゴリズムの仕組みを身につけるという使い分けが現実的です。
5.1 ほぼ整列済みデータに強い
Insertion Sortは、ほぼ整列済みのデータに対して効率よく動作しやすいアルゴリズムです。配列がすでに正しい順序に近い場合、各要素を挿入するために大きく移動させる必要がありません。そのため、内側のwhileループがほとんど実行されず、処理回数を抑えられます。新しい要素が少しだけ追加された配列や、ほとんど並んでいる配列を調整するような状況では、この特徴が分かりやすく現れます。
ただし、ほぼ整列済みデータに強いからといって、常にInsertion Sortを実務で使うべきという意味ではありません。多くの実務ケースでは、JavaScript標準のArray.prototype.sort()を使う方が読みやすく、最適化も期待できます。Insertion Sortの強みは、アルゴリズムの性質として理解しておくことが大切です。どのような入力データで処理が軽くなるのかを知ることで、ソートアルゴリズムを比較する力が身につきます。
5.2 小さな配列で理解しやすい
Insertion Sortを学ぶときは、[3, 1, 2]や[5, 3, 8, 1]のような小さな配列で処理を追うのがおすすめです。要素数が少ない配列であれば、どの値がcurrentになり、どの要素が右へずれ、どこに挿入されるのかを簡単に確認できます。最初から大きな配列で試すと、インデックスの動きや配列の変化が分かりにくくなるため、まずは短い配列で基本動作を理解しましょう。
学習時には、console.logを使ってループごとの配列の状態を出力するのも有効です。currentの値、jの位置、配列全体の変化を確認すると、Insertion Sortの動きが視覚的に理解できます。ただし、学習用のログは完成したコードには残さないようにしましょう。小さな配列で処理を追い、仕組みを理解してからコードを整理することで、アルゴリズムの理解と実装力の両方を高められます。
5.3 実務では標準sortと使い分ける
通常の実務では、自分でInsertion Sortを書くよりも、JavaScript標準のArray.prototype.sort()を使う方が一般的です。標準メソッドはJavaScriptエンジン側で最適化されており、読みやすく保守しやすいコードになります。商品一覧、ユーザー一覧、記事一覧、ランキングなどを並び替える場合は、比較関数を正しく設計してsort()を使うのが現実的です。自作のInsertion Sortを実務コードに入れる必要は、ほとんどありません。
一方で、Insertion Sortを学ぶことは、標準sort()を使ううえでも役立ちます。比較関数が何をしているのか、配列の要素がどのように並び替えられるのか、入力データの状態によって処理量が変わることなどを理解できるからです。実務では標準メソッドを使い、学習ではInsertion Sortを自分で実装してアルゴリズムの基礎を身につける。この使い分けが、JavaScriptのソートを効率よく学ぶうえで重要です。
おわりに
Insertion Sortは、要素を一つずつ取り出し、ソート済み領域の適切な位置へ挿入していくソートアルゴリズムです。JavaScriptで実装しやすく、ソート済み領域、挿入位置、要素移動、一時保存といった配列操作の基本を学ぶのに適しています。トランプの手札を並べるようなイメージで理解できるため、初心者にも比較的分かりやすいアルゴリズムです。
平均ケースや最悪ケースではO(n^2)となるため、大規模でランダムなデータには向いていません。しかし、ほぼ整列済みの小さなデータに対しては効率よく動作することがあります。この特徴は、Bubble SortやSelection Sortとの違いを理解するうえでも重要です。Insertion Sortを学ぶことで、JavaScriptの配列操作とソートアルゴリズムへの理解が深まります。次にMerge SortやQuick Sortへ進むと、より効率的なソート手法や計算量の考え方をさらに学べるでしょう。
