他山之石

データ構造とアルゴリズムの学習は、より優れたパフォーマンスのコードを書くのに役立ちます。

基礎はあなたが達成できる可能性を決定し、ビジネスはあなたの最低限の制約を決定します。

JavaScript の一般的なアルゴリズムを理解し学習することは、フロントエンド開発者がより優れたパフォーマンスのコードを書くのに役立ちます。この記事では、選択ソートと挿入ソートという 2 つの時間計算量が O (n^2) のソートアルゴリズムについて説明します。

選択ソート#

選択ソートの原理は、ソートされた配列を走査し、走査中に現在のインデックス以降の配列を走査し、最小の要素のインデックスを見つけ、現在のインデックスと最小の要素のインデックスに対応する要素を交換することです。

function swap(arr, a, b) {
  [arr[a], arr[b]] = [arr[b], arr[a]];
}

function selectionSort(arr) {
  for (let i = 0, len = arr.length; i < len; i ++) {
    let minIndex = i;
    for(let j = i + 1; j < len; j++) {
      if(arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    swap(arr, i, minIndex);
  }
}

選択ソートは 2 重のループを含んでいるため、時間計算量は O (n^2) です。

挿入ソート#

挿入ソートの原理は、トランプを並べ替える際にカードのサイズに基づいて順序を整理するのと似ています。配列の最初の要素から走査を開始し、走査中に現在のインデックスの左側の配列を右から左に比較し、左側の項目が右側の項目よりも大きい場合は交換します。そうでなければ、現在のループを終了します。以下にコードの実装例を示します。

function insertionSort(arr) {
  // 1から開始
  for (let i = 1, len = arr.length; i < len; i ++) {
    // 適切な挿入位置を探す
    for (let j = i; j > 0; j --) {
      if (arr[j] < arr[j - 1]) {
        swap(arr, j, j - 1);
      } else {
        break; // 現在のループを終了
      }
    }
  }
}

内側のループでは、2 つの項目の比較操作を for ループ内に配置することで、コードを簡素化しています。

function insertionSort(arr) {
  // 1から開始
  for (let i = 1, len = arr.length; i < len; i ++) {
    // 適切な挿入位置を探す
    for (let j = i; j > 0 && arr[j] < arr[j - 1]; j --) {
      swap(arr, j, j - 1);
    }
  }
}

選択ソートと挿入ソートを比較すると、両方とも 2 重のループを含んでおり、時間計算量は O (n^2) ですが、コードから見ると、挿入ソートは内側のループを早期に終了することができるため、挿入ソートの方が速いのでしょうか？

ソート時間のテスト#

さて、2 つのソートアルゴリズムをテストして、挿入ソートが選択ソートよりも速いかどうかを確認しましょう。

このテストでは、コードの実行にかかる時間を計測するために console.time と console.timeEnd を使用します。console.time メソッドは計測を開始し、console.timeEnd メソッドは計測を停止し、コードの実行時間を出力します。
使用方法は次の通りです：

// 計測開始
console.time('test');

// 時間を計測するコード

// 計測終了、時間を出力
console.timeEnd('test');

// test:4522.303ms

これらのメソッドは、計測器の名前を引数として受け取ります。

次のコードを作成して、テストコードを実行します：

function testFuncTime(tag, fn, args) {
  console.time(tag);
  fn(args);
  console.timeEnd(tag);
}

testFuncTime は 3 つの引数を受け取ります。計測器の名前、テストする関数、テスト関数の引数です。

結果を明確にするために、任意の範囲のランダムな数値の配列を生成するメソッドが必要です。

function getRandom(start, end, n) {
  let arr = [];
  for(let i=0; i<n; i++) {
    let choice = end - start + 1;
    let value = Math.floor(Math.random() * choice + start);
    arr.push(value);
  }
  return arr;
}

start と end の範囲内で n 個のランダムな数値の配列を生成する getRandom メソッドを作成します。

以下はテストコードです：

let array = getRandom(1, 10000, 1000);
let array2 = [...array];

testFuncTime('selectionSort', selectionSort, array);
testFuncTime('insertionSort', insertionSort, array2);

console.log(array);
console.log(array2);

上記のコードでは、1 から 10000 までの範囲で長さ 1000 のランダムな数値の配列 array を生成し、それをコピーして array2 に代入し、testFuncTime を実行してテストし、最終的にソート結果を出力します。
結果は以下の通りです：

挿入ソートの実行時間が選択ソートの約 3 倍であることがわかります。予想とは逆ですが、なぜでしょうか？

その理由は、選択ソートでは内側のループで最小値のインデックスを 1 回取得し、1 回の交換操作のみが必要です。一方、挿入ソートでは内側のループで右から左に比較し、交換操作が行われます。交換操作は非常に時間がかかるため、実行時間が長くなります。

次に、挿入ソートの実装を最適化します。

挿入ソートの最適化#

function insertionSort(arr) {
  // 1から開始
  for (let i = 1, len = arr.length; i < len; i ++) {
    // 適切な挿入位置を探す
    let e = arr[i];
    let j; // jは要素eを挿入する位置を保存する
    for (j = i; j > 0 && arr[j - 1] > e; j --) {
      arr[j] = arr[j - 1];
    }
    arr[j] = e;
  }
}

上記のコードでは、挿入ソートを最適化し、外側のループでは、現在の要素を保存するために変数 e を宣言し、要素 e を挿入する位置を保存するために変数 j を宣言しています。内側のループでは、左から右に移動しながら 2 つの項目を比較し、変数 j を左に移動させ、ループが終了するまで続けます。最後に、ソートされていない要素 e を arr [j] に代入します。

新しい変数を宣言し、交換操作を代入操作に置き換えることで、パフォーマンスを最適化しました。次に、最適化後のコードをテストします。

上記の画像からわかるように、最適化後の挿入ソートの実行時間は選択ソートの約半分になり、パフォーマンスが大幅に向上しました。

まとめ#

この記事では、O (n^2) の時間計算量を持つ 2 つのソートアルゴリズムを JavaScript で実装しました。選択ソートには 2 重のループが必要であり、どの条件でも非常に遅いため、効率が悪いです。一方、挿入ソートは最悪の場合でも O (n^2) の時間計算量ですが、実際のアプリケーションでは、O (n^2) の時間計算量のソートアルゴリズムは有用です。より複雑なソートアルゴリズムのサブプロセスとして最適化することができます。また、ほぼソートされた配列（システムログのように時間順に生成される）では、O (nlogn) のソートアルゴリズムよりも高速です。完全にソートされた配列では、挿入ソートの時間計算量は O (n) になります。