삽입 정렬은 각 숫자를 적절한 위치에 삽입해 정렬하는 알고리즘 중 하나입니다. 구현이 간단하고, 정렬이 거의 된 상태에서는 매우 효율적입니다. 하지만, 역순으로 정렬된 데이터가 입력으로 들어올 경우 최악의 경우 시간 복잡도가 O(n^2)에 달합니다.(선택 정렬에 비해 효율적)

동작 방식

삽입 정렬은 배열을 정렬하는 알고리즘 중 하나로, 각 숫자를 적절한 위치에 삽입하는 방법으로 동작합니다.

1. 삽입 정렬은 두 개의 서브 배열로 나눕니다. 정렬된 부분과 정렬되지 않은 부분입니다. 초기 상태에서는 정렬된 부분이 비어있는 상태입니다.
2. 정렬되지 않은 부분에서 한 요소를 선택합니다.
3. 이 요소를 정렬된 부분에서 적절한 위치를 찾아 삽입합니다.
4. 정렬되지 않은 부분이 더 이상 없을 때까지 2~3 과정을 반복합니다.

구현 방법

삽입 정렬은 다음과 같은 구현 방법으로 구현할 수 있습니다.

function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key; // key는 삽입 할 데이터를 가지고 있다.
  }
  return arr;
}

const arr = [5, 2, 4, 6, 1, 3];
const sortedArr = insertionSort(arr);
console.log(sortedArr); // [1, 2, 3, 4, 5, 6]

삽입 정렬은 이중 반복문을 사용합니다. 바깥쪽 반복문은 정렬되지 않은 부분을 순회하며, 안쪽 반복문은 현재 요소를 정렬된 부분의 적절한 위치에 삽입하기 위해 순회합니다.

시간 복잡도는 최선, 평균, 최악 모두 O(n^2) 입니다. 대부분의 요소가 이미 정렬된 경우에는 빠르게 동작할 수 있습니다. 따라서, 정렬해야 할 데이터의 양이 적을 경우에 유용하게 사용될 수 있습니다.