Insertion Sort

Concept

두 번째 요소부터 시작하여 그 왼쪽 값과 비교하여 Swap하고, 그 값이 왼쪽으로 갈 수 있을 때까지 비교 및 swap을 한다

선택, 버블 정렬보다 로직은 더 간단하더라도, 시간 복잡도는 같다.

How to work

1. 2번째 index 부터 Outer loop 시작 (1 -> n-1)
2. 2번째 index의 요소를 임시로 저장
3. Inner loop 시작 (i - 1 -> j >= 0 && arr[j] > value)
   
   3-1. j에 위치한 값을 값을 j + 1 위치한 값으로 대체
4. j + 1 위치한 곳에 2번에 임시로 저장한 값을으로 대체

Performance

Worst:

Average:

Best: O(n)

Source

function sortByInsertion(arr) {
  let value, i, j;
  for (i = 1; i < arr.length; i++) {
    value = arr[i];
    for (j = i - 1; j >=0 && arr[j] > value; j--) {
      arr[j + 1] = arr[j]
    }
    arr[j+1] = value
  }
}

const arr = [4, 2, 6, 3, 9, 8, 5, 7];
sortByInsertion(arr);
console.log(arr); // [2,3,4,5,6,7,8,9]