삽입 정렬(Insertion Sort)의 원리와 구현 - soo:bak

작성일 :

삽입 정렬이란?

[5, 2, 4, 6, 1, 3] 같은 정렬되지 않은 배열이 있을 때, 이를 정렬하는 방법은 여러 가지가 있습니다.

모든 원소를 비교하며 정렬할 수도 있고, 작은 값을 찾아 앞으로 보낼 수도 있습니다.


삽입 정렬(Insertion Sort)은 카드를 한 장씩 받아 정렬하는 방식과 유사한 알고리듬입니다.

배열을 정렬된 부분과 미정렬 부분으로 나누고, 미정렬 부분의 원소를 하나씩 꺼내어 정렬된 부분의 적절한 위치에 삽입합니다.

삽입 정렬의 원리

삽입 정렬은 다음과 같은 과정으로 동작합니다:

  1. 초기 상태: 첫 번째 원소를 정렬된 부분으로 간주
  2. 선택: 미정렬 부분의 첫 번째 원소를 선택
  3. 비교 및 이동: 정렬된 부분의 원소들과 비교하며, 선택한 원소보다 큰 원소들을 오른쪽으로 이동
  4. 삽입: 적절한 위치를 찾으면 선택한 원소를 삽입
  5. 반복: 2~4번 과정을 모든 원소에 대해 반복


각 단계에서 정렬된 부분은 항상 정렬 상태를 유지하며, 미정렬 부분의 원소가 하나씩 정렬된 부분으로 편입됩니다.


단계별 예시

배열 [5, 2, 4, 6, 1, 3]을 정렬하는 과정입니다:

초기: [5 | 2, 4, 6, 1, 3]

1단계: 2 삽입

  • 2 < 5 → 5를 오른쪽으로 이동
  • [2, 5 | 4, 6, 1, 3]

2단계: 4 삽입

  • 4 < 5 → 5를 오른쪽으로 이동
  • [2, 4, 5 | 6, 1, 3]

3단계: 6 삽입

  • 6 > 5 → 현재 위치 유지
  • [2, 4, 5, 6 | 1, 3]

4단계: 1 삽입

  • 모든 원소보다 작음 → 맨 앞에 삽입
  • [1, 2, 4, 5, 6 | 3]

5단계: 3 삽입

  • 2 < 3 < 4 → 2와 4 사이에 삽입
  • [1, 2, 3, 4, 5, 6]

구현

기본 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <bits/stdc++.h>
using namespace std;

void insertionSort(vector<int>& arr) {
  int n = arr.size();
  
  // 두 번째 원소부터 시작 (첫 번째는 이미 정렬된 것으로 간주)
  for (int i = 1; i < n; i++) {
    int key = arr[i];  // 삽입할 원소
    int j = i - 1;
    
    // key보다 큰 원소들을 오른쪽으로 이동
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    
    // 적절한 위치에 key 삽입
    arr[j + 1] = key;
  }
}

int main() {
  vector<int> arr = {5, 2, 4, 6, 1, 3};
  
  insertionSort(arr);
  
  for (int x : arr) cout << x << " ";
  cout << "\n";
  
  return 0;
}


핵심 포인트:

  • i는 현재 삽입할 원소의 위치
  • key는 삽입할 원소의 값
  • j는 정렬된 부분에서 비교할 위치
  • key보다 큰 원소들을 오른쪽으로 이동시키며 삽입 위치 확보


최적화된 구현 (조기 종료)

현재 원소가 이미 올바른 위치에 있다면 굳이 비교할 필요가 없습니다.

바로 앞 원소가 현재 원소보다 작거나 같으면, 이미 정렬된 상태이므로 삽입 과정을 건너뛸 수 있습니다.


예를 들어, [1, 2, 5, 3, 4]에서 5는 이미 올바른 위치에 있습니다:

  • arr[2] = 5, arr[1] = 2
  • 2 <= 5 → 이미 정렬됨, 건너뜀

이는 거의 정렬된 데이터에서 성능을 크게 향상시킵니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void insertionSort(vector<int>& arr) {
  int n = arr.size();
  
  for (int i = 1; i < n; i++) {
    int key = arr[i];
    
    // key가 이미 정렬된 위치에 있으면 건너뜀
    if (arr[i - 1] <= key) continue;
    
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}


이진 탐색을 활용한 구현

기본 삽입 정렬은 삽입 위치를 찾기 위해 정렬된 부분을 순차적으로 탐색합니다.

이 때, 이진 탐색을 사용하면 삽입 위치를 더 빠르게 찾을 수 있습니다.


예를 들어, [1, 3, 5, 7, 9]에 4를 삽입한다면:

  • 순차 탐색: 9 > 4, 7 > 4, 5 > 4, 3 < 4 → 4번 비교
  • 이진 탐색: 중간값 5 > 4, 왼쪽 중간값 3 < 4 → 2번 비교


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

void insertionSortBinary(vector<int>& arr) {
  int n = arr.size();
  
  for (int i = 1; i < n; i++) {
    int key = arr[i];
    
    // 이진 탐색으로 삽입 위치 찾기
    int left = 0, right = i - 1;
    int pos = i;
    
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (arr[mid] > key) {
        pos = mid;
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    
    // 원소들을 오른쪽으로 이동
    int temp = arr[i];
    for (int j = i; j > pos; j--) {
      arr[j] = arr[j - 1];
    }
    arr[pos] = temp;
  }
}


시간 복잡도 분석:

  • 비교 횟수: \(O(\log n)\) (이진 탐색)
  • 이동 횟수: \(O(n)\) (원소들을 한 칸씩 이동)
  • 전체: \(O(n^2)\)


이진 탐색으로 비교 횟수는 줄어들지만, 원소를 실제로 이동시키는 작업은 여전히 필요하므로 전체 시간 복잡도는 \(O(n^2)\)입니다.

다만 비교 연산이 매우 복잡한 경우(예: 문자열 비교)에는 비교 횟수를 줄이는 것만으로도 실질적인 성능 향상을 얻을 수 있습니다.

시간 복잡도

삽입 정렬의 시간 복잡도는 입력 데이터의 정렬 상태에 따라 달라집니다.


최선 시간 복잡도: \(O(n)\)

배열이 이미 정렬되어 있는 경우입니다.


예를 들어 [1, 2, 3, 4, 5]를 정렬할 때:

  • 2는 1과 비교 → 1번
  • 3은 2와 비교 → 1번
  • 4는 3과 비교 → 1번
  • 5는 4와 비교 → 1번

각 원소는 바로 앞 원소와 한 번만 비교하므로, 총 \(n-1\)번의 비교로 정렬이 완료됩니다.


평균 시간 복잡도: \(O(n^2)\)

무작위로 섞인 배열의 경우, 평균적으로 각 원소는 정렬된 부분의 절반 정도를 탐색합니다.

\[T(n) = \frac{1 + 2 + 3 + \cdots + (n-1)}{2} = \frac{n(n-1)}{4} = O(n^2)\]


최악 시간 복잡도: \(O(n^2)\)

배열이 역순으로 정렬된 경우입니다.


예를 들어 [5, 4, 3, 2, 1]을 정렬할 때:

  • 4는 5와 비교 → 1번
  • 3은 5, 4와 비교 → 2번
  • 2는 5, 4, 3과 비교 → 3번
  • 1은 5, 4, 3, 2와 비교 → 4번

각 원소는 정렬된 부분 전체를 탐색해야 하므로, 총 \(1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2}\)번의 비교가 필요합니다.


공간 복잡도

삽입 정렬은 제자리 정렬(In-place Sort)로, 원본 배열 내에서 정렬이 이루어집니다.


추가로 필요한 메모리는 다음과 같습니다:

  • key 변수: 삽입할 원소를 임시 저장
  • i, j 변수: 인덱스 관리

이들은 입력 크기와 무관한 상수 개의 변수이므로, 공간 복잡도는 \(O(1)\)입니다.

삽입 정렬의 특징


장점

  • 직관적 구조: 구현이 간단하고 이해하기 쉬움
  • 안정 정렬: 같은 값을 가진 원소들의 상대적 순서 유지
  • 제자리 정렬: 추가 메모리가 거의 필요하지 않음
  • 적응적 성능: 거의 정렬된 데이터에서 \(O(n)\)에 근접
  • 작은 데이터에 효율적: 오버헤드가 적어 작은 배열에서 빠름


단점

  • 느린 평균 성능: 평균 및 최악의 경우 \(O(n^2)\)
  • 대규모 데이터 부적합: 데이터가 클수록 성능 저하
  • 많은 이동 연산: 원소를 하나씩 이동시켜야 하므로 비용이 큼


다른 정렬과 비교

특성 삽입 정렬 선택 정렬 버블 정렬 빠른 정렬
평균 시간 복잡도 \(O(n^2)\) \(O(n^2)\) \(O(n^2)\) \(O(n \log n)\)
최선 시간 복잡도 \(O(n)\) \(O(n^2)\) \(O(n)\) \(O(n \log n)\)
최악 시간 복잡도 \(O(n^2)\) \(O(n^2)\) \(O(n^2)\) \(O(n^2)\)
공간 복잡도 \(O(1)\) \(O(1)\) \(O(1)\) \(O(\log n)\)
안정성 안정 불안정 안정 불안정
거의 정렬된 데이터 매우 빠름 느림 빠름 보통
작은 데이터 효율적 보통 비효율적 오버헤드 있음

삽입 정렬의 활용


1. 작은 데이터 정렬

데이터 크기가 작을 때 (일반적으로 10~50개 이하) 간단한 구조로 빠르게 동작합니다.

많은 고급 정렬 알고리듬이 부분 배열이 작아지면 삽입 정렬로 전환합니다.


2. 거의 정렬된 데이터

데이터가 거의 정렬되어 있을 때 \(O(n)\)에 가까운 성능을 보입니다.


예를 들어 [1, 2, 3, 5, 4, 6, 7]을 정렬할 때:

  • 대부분의 원소는 이미 올바른 위치에 있음
  • 4만 한 칸 이동하면 됨
  • 총 비교 횟수: 약 7번 (거의 \(O(n)\))

반면 완전히 섞인 배열이었다면 \(O(n^2)\)의 비교가 필요했을 것입니다.


3. 온라인 알고리듬

데이터가 순차적으로 들어오는 상황에서 새로운 데이터를 실시간으로 정렬된 위치에 삽입할 수 있습니다.


예를 들어, 실시간으로 숫자가 입력될 때:

1
2
3
4
5
6

현재 정렬된 배열: [1, 3, 5, 7]
새 입력: 4
→ [1, 3, 4, 5, 7] (바로 삽입)

새 입력: 6  
→ [1, 3, 4, 5, 6, 7] (바로 삽입)

삽입 정렬의 한 단계만 수행하면 되므로, 각 입력마다 \(O(n)\) 시간에 처리할 수 있습니다.

1
2
3
4
5
6

vector<int> sorted;

void insertInSorted(int value) {
  auto pos = upper_bound(sorted.begin(), sorted.end(), value);
  sorted.insert(pos, value);
}


4. 하이브리드 정렬의 부분 알고리듬

Tim Sort, Introsort 등에서 작은 부분 배열을 정렬할 때 사용됩니다.


예를 들어, 빠른 정렬이 재귀적으로 분할하다가 부분 배열 크기가 10개 이하가 되면:

  • 빠른 정렬 계속: 재귀 호출 오버헤드 발생
  • 삽입 정렬로 전환: 간단한 반복문으로 빠르게 처리

작은 배열에서는 삽입 정렬의 간단한 구조가 재귀 오버헤드보다 효율적이기 때문입니다.

실전 예제: 정렬된 배열에 새 원소 삽입

문제

정렬된 배열에 새로운 원소를 정렬 상태를 유지하며 삽입하는 프로그램을 작성하시오.


접근법

삽입 정렬의 한 단계를 수행합니다.

배열의 끝에서부터 시작하여 새 원소보다 큰 원소들을 오른쪽으로 이동시키고, 적절한 위치에 삽입합니다.


구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <bits/stdc++.h>
using namespace std;

void insertElement(vector<int>& arr, int value) {
  // 배열 끝에 임시로 추가
  arr.push_back(value);
  
  int i = arr.size() - 2;  // 마지막 원소의 이전 위치
  int key = value;
  
  // key보다 큰 원소들을 오른쪽으로 이동
  while (i >= 0 && arr[i] > key) {
    arr[i + 1] = arr[i];
    i--;
  }
  
  // 적절한 위치에 삽입
  arr[i + 1] = key;
}

int main() {
  vector<int> arr = {1, 3, 5, 7, 9};
  
  cout << "Original: ";
  for (int x : arr) cout << x << " ";
  cout << "\n";
  
  insertElement(arr, 6);
  
  cout << "After inserting 6: ";
  for (int x : arr) cout << x << " ";
  cout << "\n";
  
  return 0;
}


출력:

1
2

Original: 1 3 5 7 9
After inserting 6: 1 3 5 6 7 9


시간 복잡도: \(O(n)\) (최악의 경우 모든 원소를 이동)

마무리

삽입 정렬은 배열을 정렬된 부분과 미정렬 부분으로 나누고, 미정렬 부분의 원소를 하나씩 정렬된 위치에 삽입하는 알고리듬입니다.


평균 및 최악의 경우 \(O(n^2)\)의 시간 복잡도를 가지지만, 이미 정렬된 데이터에서는 \(O(n)\)에 가까운 성능을 보입니다.

안정 정렬이며 제자리 정렬로 추가 메모리가 거의 필요하지 않습니다.


작은 데이터나 거의 정렬된 데이터에 효율적이며, Tim Sort나 Introsort 같은 하이브리드 정렬의 부분 알고리듬으로도 사용됩니다.

간단한 구조와 적응적 특성 때문에 특정 상황에서는 더 복잡한 알고리듬보다 우수한 성능을 발휘합니다.


관련 글:


관련 문제:

이 블로그의 다른 글