[알고리즘] 삽입 정렬(Insertion Sort)

1. 개념

• 삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어 진행하는 알고리즘이다.
• 하나의 원소를 꺼내 이미 정렬된 부분에서 적절한 위치를 찾아 삽입하면서 전체 배열을 점차 정렬해 나간다.
• 버블 정렬이나 선택 정렬과 비슷한 기초 정렬 알고리즘이지만, 특정 상황에서는 더 효율적으로 작동한다.

---

2. 동작 방식

동작 예시

정렬할 배열: [5, 3, 4, 1, 2]

1. 첫 번째 원소는 이미 정렬된 부분으로 간주한다
2. [5] | [3, 4, 1, 2] (정렬된 부분 | 정렬되지 않은 부분)
3. 두 번째 원소(3) → 정렬된 부분과 비교
   • 5보다 작으므로 앞으로 이동한다.

   [3, 5] | [4, 1, 2]

4. 세 번째 원소(4) → 정렬된 부분과 비교
   • 5보다 작고, 3보다는 크므로 3과 5 사이에 삽입한다.

   [3, 4, 5] | [1, 2]

5. 네 번째 원소(1) → 정렬된 부분과 비교
   • 5, 4, 3 모두보다 작으므로 맨 앞으로 이동한다.

   [1, 3, 4, 5] | [2]

6. 다섯 번째 원소(2) → 정렬된 부분과 비교
   • 5보다 작음 → 이동
   • 4보다 작음 → 이동
   • 3보다 작음 → 이동
   • 1보다는 크므로 1 뒤에 삽입한다.

   [1, 2, 3, 4, 5]

 

👉 이런 식으로 "정렬된 부분"을 점점 확장해 가면서, 매 단계마다 현재 원소를 올바른 위치에 삽입하는 것이 삽입 정렬의 핵심이다.

---

의사 코드

1. 첫 번째 원소는 이미 정렬되어 있다고 가정한다.
2. 두 번째 원소부터 시작해, 현재 원소(currentVal)를 정렬된 부분과 비교한다.
3. 비교 과정에서 자신보다 큰 원소를 만나면 그 원소를 오른쪽으로 한 칸씩 이동시킨다.
4. 더 이상 이동할 필요가 없을 때, 비워진 위치에 currentVal을 삽입한다.
5. 배열의 끝까지 이 과정을 반복하면 정렬이 완료된다.

function 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;
}

 

예시

정렬할 배열: [2, 1, 9, 76, 4]

• 2 → 이미 정렬된 부분
• 1 → 2보다 작으므로 앞으로 삽입 → [1, 2, 9, 76, 4]
• 9 → 올바른 위치에 있음 → [1, 2, 9, 76, 4]
• 76 → 올바른 위치에 있음 → [1, 2, 9, 76, 4]
• 4 → 76보다 작으므로 앞으로 이동 → [1, 2, 4, 9, 76]

---

시간 복잡도

• 최선의 경우: O(n)
  • 배열이 이미 정렬되어 있는 경우, 한 번 비교만으로 다음 단계로 넘어갈 수 있다.
• 평균/최악의 경우: O(n²)
  • 배열이 무작위이거나 역순으로 정렬되어 있을 때 많은 비교와 이동이 발생한다.

---

공간 복잡도

• O(1)
  • 추가 메모리를 거의 사용하지 않는다.

---

특징 및 장점

• 작은 데이터셋에서는 효율적이다.
• 거의 정렬된 데이터에서 매우 빠르게 작동한다.
• 새로운 데이터가 들어올 때마다 즉시 적절한 위치에 삽입 가능하다.
• 구현이 간단하고 직관적이다.

---

👉 결론적으로, 삽입 정렬은 단순하고 직관적이며 작은 크기의 데이터나 이미 정렬에 가까운 데이터에서 강점을 발휘하는 알고리즘이다.