JavaScriptで挿入ソートを実装して数値配列を昇順に並べ替える方法

挿入ソートとは

挿入ソート（Insertion Sort）は、シンプルで直感的なソートアルゴリズムの一つです。配列を「整列済みの部分」と「未整列の部分」に分け、未整列部分の要素を一つずつ取り出して、整列済み部分の適切な位置に挿入していくことで全体を並べ替えます。

データ量が少ない場合や、すでにほぼ整列されたデータに対しては非常に効率的に動作するため、実務でも場面を選んで活用されています。

問題の概要

今回は、JavaScript関数を作成します。この関数は、第一引数（唯一の引数）として数値の配列 arr を受け取ります。

関数の役割は、挿入ソートのアルゴリズムを使用して、この数値配列を昇順（小さい順）に並べ替えることです。

入力例

const arr = [5, 8, 1, 3, 9, 4, 2, 7, 6];

出力例

const output = [1, 2, 3, 4, 5, 6, 7, 8, 9];

挿入ソートの実装コード

以下が、挿入ソートを実装したJavaScriptのコードです。

const arr = [5, 8, 1, 3, 9, 4, 2, 7, 6];

const insertionSort = (arr = []) => {
    let n = arr.length;
    for (let i = 1; i < n; i++) {
        // 現在注目している要素を保存
        let curr = arr[i];
        let j = i - 1;

        // 前方の要素が現在の要素より大きい間、後ろへずらす
        while ((j > -1) && (curr < arr[j])) {
            arr[j + 1] = arr[j];
            j--;
        }

        // 適切な位置に現在の要素を挿入
        arr[j + 1] = curr;
    };
    return arr;
}

console.log(insertionSort(arr));

実行結果

[1, 2, 3, 4, 5, 6, 7, 8, 9]

アルゴリズムの解説

このコードの動作を順番に見ていきましょう。

1. ループの開始位置： 外側の for ループはインデックス 1 から始まります。これは、先頭の最初の要素はそれ単体で「整列済み」とみなせるためです。
2. 現在の要素の保存： 変数 curr に現在の要素を保存しておきます。後続の処理で要素をずらす際に値が上書きされても、元の値を保持できるようにするためです。
3. 要素の比較と移動： while ループ内で、前方の要素 arr[j] が現在の要素 curr より大きい限り、その要素を一つ後ろへ移動させます。同時に j を減算して、さらに前の要素との比較へ進みます。
4. 挿入： ループが終了した時点で j + 1 の位置が、現在の要素を挿入すべき適切な位置となります。

計算量について

• 最悪計算量： O(n²) — 配列が逆順に並んでいる場合など
• 最良計算量： O(n) — 配列がすでに整列されている場合
• 空間計算量： O(1) — 入力配列を直接書き換えるインプレースソートのため追加メモリが不要

挿入ソートは安定ソートであり、等しい値を持つ要素同士の相対的な順序が保たれる点も特徴です。小規模なデータセットや、ほぼ整列済みのデータに対しては、クイックソートなどの高度なアルゴリズムよりも高速に動作することもあります。