Algorithm / 정렬 / Insertion Sort (삽입 정렬)

삽입 정렬

function insertion_sort(arr) {
  console.log(`Before insertion sorting: ${[...arr]}`);
  let cnt = 0;

  for (var i = 1; i < arr.length; i++) {
    const cur = arr[i];

    for (var j = i - 1; j >= 0 && arr[j] > cur; j--) {
      if (cur < arr[j]) arr[j + 1] = arr[j];
      cnt++;
    }

    arr[j + 1] = cur;
  }

  console.log(`After insertion sorting: ${[...arr]}`);
  console.log(`Sorting count = ${cnt}`);
}

let arr = [3, 6, 13, 4, 33, 12, 35, 87, 6, 64];
insertion_sort(arr);

---

시간 복잡도: O(n^2)

• 가장 최선의 시간 복잡도는 O(n) 이다.
• 가장 최선의 시간 복잡도를 가질 때에는 (거의)다 정렬된 경우에 정렬을 수행할 때이다.
• 평균과 최악의 시간 복잡도가 O(n^2) 이다.
• 따라서 데이터가 하나씩 새로 들어오면 정렬을 수행해야 할 때 적합한 정렬 방법이다.
  • 처음에 정렬할 때만 위의 시간 복잡도를 가지며,
  • 그 뒤에 데이터가 들어올때는 이미 정렬된 곳에 비교하여 집어넣기만 하면되므로 적합하다.