ソート・アルゴリズム-ソートの挿入

4999 ワード
アルゴリズム#アルゴリズム# テキストリンク

挿入


要素をソートするには、左から右の順に比較します.

時間の複雑さ

  • 最適:O(n)、並べ替えられた
  • 最悪:O(n^2)、ソートなし

    • 長所

  • 挿入ソートは、Bubbleソートと同様に、in placeアルゴリズムを使用してメモリを節約します.
  • の実装は非常に簡単であり、ソートされたデータであればO(n)回を巡回するだけでよいので、ソートされたかどうかをテストするために使用することができる.

    • 短所

  • 挿入ソートも同様に資料数の増加に伴って性能が低下する.

    • インプリメンテーション

    'use strict';

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const cur = arr[i];
    let leftIdx = i - 1;

    while (leftIdx >= 0 && arr[leftIdx] > cur) {
      [arr[leftIdx], arr[leftIdx + 1]] = [arr[leftIdx + 1], arr[leftIdx]];

      leftIdx--;
    }

    console.log(`${i}회전 : ${arr}`);
  }

  return arr;
}

console.log(insertionSort([3, 7, 2, 5, 1, 4]));
    TIL-041|デコレーションして、ホームズプロジェクト(4)メニュービュー、商品リストを実現
    バックエンドとの初回データ通信