[JS] 삽입 정렬

삽입 정렬은 값의 비교를 앞의 요소들과 비교하여 삽입하는 정렬 알고리즘이다.

4를 currentVal 변수에 저장해두고 5랑 비교한다. currentVal과 비교 했을 때 5가 더 크므로 4가 있던 자리에 5를 저장한다. 그러면 아래와 같이 된다.

// [3,5,5,1,2]

3과 비교했을 때 4가 더 크므로 원래 5가 있던 자리에 4를 저장한다. 이를 코드로 적으면 다음과 같다.

function insertionSort(arr) {
  let currentVal;
  for (let i = 1; i < arr.length; i++) {
    currentVal = arr[i];
    for (let j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = currentVal;
  }
  return arr;
}

const arr = insertionSort([2, 1, 9, 76, 4]);
console.log(arr);

외부 반복문은 두 번째 요소부터 시작한다. 내부 반복문은 앞의 요소와 비교해야 하므로 외부 반복문보다 앞선 요소부터 처음까지 반복한다.

그림 보면 이해 될지도 모르겠다.

시간 복잡도

최고의 경우: $O(n)$
평균의 경우: $O(n^2)$
최악의 경우: $O(n^2)$

공간 복잡도: $O(n)$