挿入

3250 ワード
algorithm テキストリンク

サマリ


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;
};
    Pagerのコンパクトなページングコントロール
    なぜインタフェースを使うのですか?