JavaScript
 Computer >> コンピューター >  >> プログラミング >> JavaScript

JavaScriptで挿入ソートを実装する方法をわかりやすく解説

挿入ソート（Insertion Sort）とは

挿入ソートは、配列を並べ替えるための非常にシンプルな比較ソートの一つです。比較ソートでは、現在ソートしようとしている値を配列内の他の値と順番に比較しながら、1つの要素ずつ処理を進めます。各要素を正しい位置へ繰り返し挿入していくことで、最終的にソート済みの配列を作り上げます。

実際のところ、挿入ソートはヒープソートやマージソートといった高度なアルゴリズムほど効率的ではありません。そのため、大規模なデータを扱う場合には必ずしも最適な選択肢とは言えません。しかし、隠れた定数項が小さいという特性を持つため、小さな配列を扱う場面では、ヒープソートやクイックソートなどの高度なアルゴリズムよりも優れたパフォーマンスを発揮することがあります。

挿入ソートは、配列の左側から右側へ向かって処理を進めます。現在注目している要素を「キー」として扱い、そのキーよりも左側にある値の中から、キーが本来収まるべき位置を探して挿入します。

計算量について

挿入ソートの平均計算量および最悪計算量はO(n²)です。一方、すでにほぼ整列済みのデータに対しては、最良ケースでO(n)という高速な動作が期待できます。この特性から、小規模なデータセットや、ほぼソート済みのデータに対して特に有効なアルゴリズムと言えます。

アルゴリズムの流れ

以下の例では、配列「0, -3, 5, 8, 2, 7, 6」をソートしていきます。

  • 反復0：最初の時点では、まだソートされていない元の配列「0, -3, 5, 8, 2, 7, 6」があるだけです。
  • 反復1：キーはインデックス1の値「-3」です。キーとその左側の値を比較します。-3は0より小さいため、0の左側へ移動し、配列は「-3, 0, 5, 8, 2, 7, 6」になります。
  • 反復2：キーはインデックス2の値「5」です。左側の値「-3」と「0」と比較されますが、すでに正しい位置にあるため配列は変化せず、「-3, 0, 5, 8, 2, 7, 6」のままです。
  • 反復3：キー値「8」が左側の要素と比較されます。ここでも8はすでに正しい位置にあるため、配列は「-3, 0, 5, 8, 2, 7, 6」のままです。
  • 反復4：キー値「2」が左側の値と比較され、正しい位置へ挿入されます。反復4の終了後、配列は「-3, 0, 2, 5, 8, 7, 6」になります。

同じ手順を最後まで繰り返すと、最終的にはソート済みの配列「-3, 0, 2, 5, 6, 7, 8」が得られます。

実装コード

<html>
<head>
<script>
    function iSort(array) {
      for (var p = 1; p < array.length; p++) {
        // キーが先頭の要素より小さい場合は先頭へ移動
        if (array[p] < array[0]) {
          array.unshift(array.splice(p, 1)[0]);
        }
        // すでに正しい位置にある場合は何もしない
        else if (array[p] > array[p - 1]) {
          continue;
        }
        // 挿入すべき位置を探して移動
        else {
          for (var q = 1; q < p; q++) {
            if (array[p] > array[q - 1] && array[p] < array[q]) {
              array.splice(q, 0, array.splice(p, 1)[0]);
            }
          }
        }
      }
      return array;
    }
    document.write(iSort([0, -3, 5, 8, 2, 7, 6]));
</script>
</body>
</html>

出力結果

-3,0,2,5,6,7,8

このように、挿入ソートはコードがシンプルで理解しやすく、小規模な配列のソートには手軽で実用的な選択肢となります。ただし、データ量が大きくなると計算量O(n²)の影響で処理が遅くなるため、用途に応じてマージソートやクイックソートなどとの使い分けを検討するとよいでしょう。

  1. JavaScriptのArray.prototype.sort()メソッドの使い方をサンプルコードで解説

    Array.prototype.sort()は、JavaScriptで配列の要素を並べ替えるための組み込みメソッドです。アルファベット順・数値順といった並び方に加えて、昇順・降順も自由に指定でき、配列操作の中でも特に使用頻度の高いメソッドの一つです。 ただし重要なポイントとして、sort()メソッドはデフォルトではすべての要素を文字列に変換してから比較します。そのため、数値の配列を意図したとおりに並べ替えたい場合は、比較関数を引数として渡す必要があります。 以下は、Array.prototype.sort()メソッドの基本的な使い方を示すサンプルコードです。 サンプルコード <!DOC

  2. 挿入ソートとは？仕組み・計算量・C++実装例をわかりやすく解説

    挿入ソートは、トランプの手札を並べ替えるときの操作によく似た整列アルゴリズムです。カードゲームで手札を昇順に整理する場面を思い浮かべてください。新しいカードを引いたら、すでに並んでいるカードの中から適切な位置を見つけて、そこに差し込みますよね。まさにこれが挿入ソートの基本的な考え方です。具体的には、データ集合から1つの要素を取り出し（この値を「キー」と呼びます）、そのキーを挿入できる隙間を作るために、左側にあるより大きい要素を順番に右へずらしていきます。そして、正しい位置が見つかったところでキーを挿入します。これを配列の末尾まで繰り返すことで、全体が昇順に整列されていきます。挿入ソートの計算量