자바스크립트의 삽입정렬(Insertion Sort)

지난 선택정렬(Selection Sort)에 이어 삽입정렬(Insertion Sort)에 대해 알아보자.

이 글은 JavaScript 알고리즘 & 자료구조 마스터클래스를 참고하여 작성되었습니다.

01. 삽입 정렬(Insertion Sort)의 개념

삽입 정렬은 가장 큰 요소를 찾아 하나씩 이동하거나, 각 루프당 가장 작은 요소를 찾아 갱신하는 대신, 각 요소를 정렬된 배열에 삽입하는 방식이다.

즉 루프당 하나의 항목을 정렬된 배열 속 올바른 위치에 삽입하여 점진적으로 정렬된 배열을 구축할 수 있도록 한다.

02. 정렬 방법

1. 먼저 배열의 두번째 요소부터 선택해 반복문을 돈다.
   → 맨 첫 번째 요소는 이미 정렬되었다고 간주하기 때문이다.
2. 따라서 두 번째 값부터 정렬된 배열과 비교하여 올바른 위치에 삽입하며 정렬한다.
3. 정렬이 끝날 때까지 위 과정을 반복한 후, 정렬된 배열을 반환한다.

03. 삽입 정렬 구현

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

console.log(insertionSort([2, 1, 9, 76, 4])); // [ 1, 2, 4, 9, 76 ]

1. 배열의 두 번째 요소부터 선택해 루프를 돌며 첫 번째 요소와 비교한다.
2. 만약 첫번 째 요소보다 작다면, 해당 요소와 위치를 교환하고 다음 루프로 넘어간다.
3. 루프를 돌면서 이미 정렬된 배열 속 요소와 비교하고 올바른 위치에 삽입하여 정렬을 마친다.

04. 삽입 정렬의 시간 복잡도(Big O)

삽입 정렬의 최선의 시간복잡도는 O(N), 최악은 O(N^2)으로 앞선 버블 정렬, 선택 정렬과 비슷하다.

하지만 삽입 정렬이 활용적인 상황이 있는데, 바로 실시간 집계되는 데이터를 정렬해야 할 때 이다.

이 경우 전체 배열을 다시 정렬할 필요 없이, 데이터가 수신되는 대로 해당 데이터 값을 기존 배열의 값과 비교하여 올바른 위치에 값을 삽입하면 되기 때문에 삽입 정렬이 매우 매우 유용하다.