メモログ

Selection Sort in JavaScriptの記事から引き続き。内容は挿入ソートからの抜粋なので詳細はそちらを参照。

挿入ソートは配列から左から順に値を取り出して、ソート済みの配列の適切な場所に値を挿入していく、ということを繰り返し行う。配列は左から順にソート済み状態となり、最後までソート済みになったところで終了。選択ソートと同じ O(n^2)であるけど、選択ソートが取り出す値を見つけるのにソートされていない値をすべて確認しなければならないのに対して、挿入ソートはソート済みの値を比較して挿入位置が見つかったらそこで確認を終えることができる。ので、挿入ソートの方が実際の効率は良いとされている。

実装例はThe Insertion sort algorithm - Ben’s BlogとV8 の array.jsを参考にしている。

テストの箇所は省略。Gistを参照してください。今回は前回のSelection Sort in JavaScriptと同じ配列を使って比較してみた。

function insertionSort(array, showArray) {
  let count = 0;
  const arrayLength = array.length;
  for (let i = 1; i < arrayLength; i++) {
    const a = array[i];
    let j = i - 1;
    for (; j >= 0; j--) {
      count++;
      const b = array[j];
      if (a < b) {
        array[j + 1] = b;
      } else {
        break;
      }
    }
    array[j + 1] = a;
    if (showArray) {
      console.log(array);
    }
  }
  console.log(`number of iterates: ${count}`);
}

実行例

> test([bubbleSort, selectionSort, insertionSort], 10, true);