삽입 정렬 (Insertion Sort) 설명과 JavaScript 예제

삽입 정렬은 정렬이 되어 있는 부분에 데이터를 삽입하는 방식으로 동작하는 정렬 알고리즘입니다. 카드 게임에서 손에 카드를 한 장씩 끼워 넣으며 정렬하는 방식과 유사해 직관적으로 이해하기 쉽습니다.

---

1. 동작 원리

1. 두 번째 요소부터 시작해서 현재 값을 임시 변수로 저장
2. 그 앞에 있는 요소들과 비교해, 자신보다 큰 값은 한 칸씩 뒤로 이동
3. 적절한 위치에 임시 값을 삽입
4. 배열의 끝까지 반복

정렬된 부분을 점차 확장해나가는 구조입니다.

---

2. JavaScript 예제 - 오름차순 정렬

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

console.log(insertionSort([5, 2, 9, 1, 5, 6])); // [1, 2, 5, 5, 6, 9]

• current: 삽입 대상 값
• j: 정렬된 영역을 역방향으로 탐색하면서 위치를 찾음
• 이동 후 적절한 위치에 삽입

---

3. 성능 분석

구분	시간 복잡도
최선의 경우	O(n)
평균	O(n^2)
최악의 경우	O(n^2)

• 최선: 이미 정렬된 배열 (한 번도 이동하지 않음)
• 공간 복잡도: O(1), 제자리 정렬 (in-place)
• 안정 정렬(stable sort): 같은 값의 원래 순서 유지됨

---

4. 삽입 정렬의 특징

• 정렬이 거의 완료된 데이터에 매우 빠름
• 데이터 양이 적거나 정렬 상태가 좋을 때는 효율적
• 코드가 간결하고 이해하기 쉬움

---

마무리

삽입 정렬은 단순하면서도 정렬 개념을 이해하기에 좋은 알고리즘입니다. 실제 정렬 라이브러리에서는 일부 구간을 삽입 정렬로 처리하기도 할 만큼, 상황에 따라 유용하게 사용될 수 있습니다.

완전히 정렬된 상태에 가까운 배열일수록 삽입 정렬의 장점이 극대화됩니다.