挿入

サマリ

2番目の要素から左の要素と比較し、指定した位置にある要素を後ろに移動して挿入してソートするアルゴリズムです.

プロセス

時間の複雑さ

Best Case: O(n)

はすべてソートされていて、一度だけ比較するので

Worst Case: O(n^2)

(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2

くうかんふくざつさ

は、与えられた配列において交換順序付けされるので、O(1)

長所

アルゴリズムは簡単です.

のソートであれば、非常に効率的です.

アレイでスワップするため、他のメモリ領域のその場ソートは必要ありません.

安定したソート.

短所

配列の長さが長ければ長いほど、効率は低下する.

コード実装

const insertionSort = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    let curVal = arr[i];
    let idx = i - 1;
    while (idx >= 0 && arr[idx] > curVal) {
      arr[idx + 1] = arr[idx];
      idx--;
    }
    arr[idx + 1] = curVal;
  }
  return arr;
};