Insertion Sort Explanation

Problem Summary

Implement insertion sort to sort an array in ascending order.

Detailed Explanation

이 문제는 **삽입 정렬(Insertion Sort)** 알고리즘을 구현하는 방법을 학습합니다. ## 핵심 개념: 삽입 정렬 카드 정렬처럼 각 요소를 정렬된 부분의 올바른 위치에 삽입합니다. ### 알고리즘 1. 두 번째 요소부터 시작 2. 현재 요소를 임시 저장 3. 정렬된 부분에서 올바른 위치 찾기 4. 요소들을 오른쪽으로 이동 5. 올바른 위치에 삽입 ### 코드 분석 ```javascript for (let i = 1; i < result.length; i++) { const key = result[i]; let j = i - 1; while (j >= 0 && result[j] > key) { result[j + 1] = result[j]; j--; } result[j + 1] = key; } ``` ### 시각화 ``` [5, 2, 4, 6, 1] [2, 5, 4, 6, 1] // 2 삽입 [2, 4, 5, 6, 1] // 4 삽입 [2, 4, 5, 6, 1] // 6 삽입 [1, 2, 4, 5, 6] // 1 삽입 ``` ### 특징 - 거의 정렬된 배열에서 매우 빠름 (O(n)) - 안정 정렬 (같은 값의 순서 유지) - 온라인 알고리즘 (실시간 정렬 가능)

Solution Code

solution.js

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

Key Concepts from This Problem

1. 삽입 정렬

2. 정렬된 부분 배열

3. 요소 이동

4. 안정 정렬

Common Mistakes

✗ key를 저장하지 않으면 이동 시 값이 사라집니다

✗ while 조건에서 j >= 0 체크가 중요합니다

✗ j + 1 위치에 삽입하는 이유를 이해해야 합니다

Hints

Hint 1: 각 요소를 정렬된 부분에 올바른 위치에 삽입하세요.

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

Uses almost no additional memory

Related Tags

#알고리즘 #정렬 #삽입정렬