삽입 정렬은 배열을 정렬된 영역과 정렬되지 않은 영역으로 나누고, 정렬되지 않은 영역에서 원소를 하나씩 꺼내어 정렬된 영역의 적절한 위치에 삽입하는 알고리즘이다. 마치 카드 게임에서 손에 든 카드를 정렬하는 방식과 유사하다. 구현이 직관적이지만 성능은 O(n²)으로 비효율적이다.
핵심 원리
- 첫 번째 원소는 이미 정렬되어 있다고 가정한다
- 정렬되지 않은 영역에서 원소를 하나씩 선택한다
- 정렬된 영역을 역순으로 탐색하며 삽입 위치를 찾는다
- 찾은 위치의 원소를 삽입한다
동작 과정 상세 분석
배열 [4, 1, 5, 3, 6, 2]를 오름차순으로 정렬하는 과정을 단계별로 살펴보자
[4 | 1, 5, 3, 6, 2]
✓ └──────────┘
정렬됨 정렬 안됨
첫 번째 원소(4)는 이미 정렬되어 있다고 가정
1단계: 1 삽입하기
삽입할 원소: 1
정렬된 영역: [4]
[4 | 1, 5, 3, 6, 2]
비교 1: 4 vs 1
→ 4 > 1이므로 4를 오른쪽으로 이동
[4 | 4, 5, 3, 6, 2]
↑ 4가 복사됨
더 이상 비교할 원소 없음
→ 1을 첫 번째 위치에 삽입
[1, 4 | 5, 3, 6, 2]
✓ ✓ └────────┘
2단계: 5 삽입하기
삽입할 원소: 5
정렬된 영역: [1, 4]
[1, 4 | 5, 3, 6, 2]
비교 1: 4 vs 5
→ 4 < 5이므로 이동 불필요
→ 5는 현재 위치가 적절함
[1, 4, 5 | 3, 6, 2]
✓ ✓ ✓ └─────┘
3단계: 3 삽입하기
삽입할 원소: 3
정렬된 영역: [1, 4, 5]
[1, 4, 5 | 3, 6, 2]
비교 1: 5 vs 3
→ 5 > 3이므로 5를 오른쪽으로 이동
[1, 4, 5 | 5, 6, 2]
↑ 5가 복사됨
비교 2: 4 vs 3
→ 4 > 3이므로 4를 오른쪽으로 이동
[1, 4, 4, 5, 6, 2]
↑ 4가 복사됨
비교 3: 1 vs 3
→ 1 < 3이므로 정지
→ 3을 1 다음 위치에 삽입
[1, 3, 4, 5 | 6, 2]
✓ ✓ ✓ ✓ └──┘
4단계: 6 삽입하기
삽입할 원소: 6
정렬된 영역: [1, 3, 4, 5]
[1, 3, 4, 5 | 6, 2]
비교 1: 5 vs 6
→ 5 < 6이므로 이동 불필요
→ 6은 현재 위치가 적절함
[1, 3, 4, 5, 6 | 2]
✓ ✓ ✓ ✓ ✓ └┘
5단계: 2 삽입하기
삽입할 원소: 2
정렬된 영역: [1, 3, 4, 5, 6]
[1, 3, 4, 5, 6 | 2]
비교 1: 6 vs 2
→ 6 > 2이므로 6을 오른쪽으로 이동
[1, 3, 4, 5, 6, 6]
↑ 6이 복사됨
비교 2: 5 vs 2
→ 5 > 2이므로 5를 오른쪽으로 이동
[1, 3, 4, 5, 5, 6]
↑ 5가 복사됨
비교 3: 4 vs 2
→ 4 > 2이므로 4를 오른쪽으로 이동
[1, 3, 4, 4, 5, 6]
↑ 4가 복사됨
비교 4: 3 vs 2
→ 3 > 2이므로 3을 오른쪽으로 이동
[1, 3, 3, 4, 5, 6]
↑ 3이 복사됨
비교 5: 1 vs 2
→ 1 < 2이므로 정지
→ 2를 1 다음 위치에 삽입
[1, 2, 3, 4, 5, 6]
✓ ✓ ✓ ✓ ✓ ✓
정렬 완료
시각적 다이어그램
═══════════════════════════════════════════════════
초기 배열
═══════════════════════════════════════════════════
[4 | 1, 5, 3, 6, 2]
✓ └──────────┘
정렬 정렬 안됨
═══════════════════════════════════════════════════
1단계: 1 삽입
═══════════════════════════════════════════════════
삽입할 원소: 1
정렬된 영역을 역순으로 탐색:
[4 | 1, 5, 3, 6, 2]
↓
4 > 1 → 4를 오른쪽으로
[4, 4, 5, 3, 6, 2]
↑
4 복사
더 이상 비교할 원소 없음
→ 맨 앞에 1 삽입
결과: [1, 4 | 5, 3, 6, 2]
✓ ✓
═══════════════════════════════════════════════════
2단계: 5 삽입
═══════════════════════════════════════════════════
삽입할 원소: 5
[1, 4 | 5, 3, 6, 2]
↓
4 < 5 → 이동 불필요
결과: [1, 4, 5 | 3, 6, 2]
✓ ✓ ✓
═══════════════════════════════════════════════════
3단계: 3 삽입
═══════════════════════════════════════════════════
삽입할 원소: 3
정렬된 영역을 역순으로 탐색:
[1, 4, 5 | 3, 6, 2]
↓
5 > 3 → 5를 오른쪽으로
↓
4 > 3 → 4를 오른쪽으로
↓
1 < 3 → 정지!
[1, 4, 4, 5, 6, 2]
↑ ↑
4 5 복사
→ 1 다음에 3 삽입
결과: [1, 3, 4, 5 | 6, 2]
✓ ✓ ✓ ✓
═══════════════════════════════════════════════════
4단계: 6 삽입
═══════════════════════════════════════════════════
삽입할 원소: 6
[1, 3, 4, 5 | 6, 2]
↓
5 < 6 → 이동 불필요
결과: [1, 3, 4, 5, 6 | 2]
✓ ✓ ✓ ✓ ✓
═══════════════════════════════════════════════════
5단계: 2 삽입
═══════════════════════════════════════════════════
삽입할 원소: 2
정렬된 영역을 역순으로 탐색:
[1, 3, 4, 5, 6 | 2]
↓
6 > 2 → 6을 오른쪽으로
↓
5 > 2 → 5를 오른쪽으로
↓
4 > 2 → 4를 오른쪽으로
↓
3 > 2 → 3을 오른쪽으로
↓
1 < 2 → 정지!
[1, 3, 3, 4, 5, 6]
↑ ↑ ↑ ↑ ↑
모든 원소가 오른쪽으로 이동
→ 1 다음에 2 삽입
결과: [1, 2, 3, 4, 5, 6]
✓ ✓ ✓ ✓ ✓ ✓
정렬 완료
Java 구현
public class InsertionSort {
/**
* 삽입 정렬 알고리즘
* @param arr 정렬할 배열
*/
public static void insertionSort(int[] arr) {
// 외부 루프: 정렬되지 않은 영역의 각 원소를 처리
// 첫 번째 원소(인덱스 0)는 이미 정렬되어 있다고 가정
for (int i = 1; i < arr.length; i++) {
// 삽입할 원소를 임시 저장
int insertionData = arr[i];
// 정렬된 영역에서 삽입 위치를 찾기 위한 인덱스
int j;
// 내부 루프: 정렬된 영역을 역순으로 탐색
for (j = i - 1; j >= 0; j--) {
// 현재 원소가 삽입할 원소보다 크면
if (arr[j] > insertionData) {
// 오른쪽으로 한 칸 이동
arr[j + 1] = arr[j];
} else {
// 삽입할 위치를 찾았으므로 탐색 종료
break;
}
}
// 찾은 위치에 원소 삽입
// j는 insertionData보다 작은 원소의 인덱스
// 따라서 j+1 위치에 삽입
arr[j + 1] = insertionData;
}
}
// 배열 출력 메서드
public static void printArray(int[] arr) {
System.out.print("[");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i < arr.length - 1) {
System.out.print(", ");
}
}
System.out.println("]");
}
// 테스트 메인 메서드
public static void main(String[] args) {
System.out.println("=== 기본 삽입 정렬 ===");
int[] arr1 = {4, 1, 5, 3, 6, 2};
System.out.println("정렬 전:");
printArray(arr1);
insertionSort(arr1);
System.out.println("정렬 후:");
printArray(arr1);
}
}
/*
실행 결과
=== 기본 삽입 정렬 ===
정렬 전:
[4, 1, 5, 3, 6, 2]
정렬 후:
[1, 2, 3, 4, 5, 6]
*/
헷갈렸던 부분
삽입 정렬에서 가장 헷갈렸던 부분은 내부 루프가 끝난 후 첫 번째 원소 위치(인덱스 0)에 insertionData를 삽입하는 방법이다.
일반적인 경우에는 내부 루프에서 작은 값을 만나면 break로 빠져나오고, 그 위치의 다음(j+1)에 insertionData를 넣습니다. 이 부분은 직관적으로 이해가 되었다.
하지만 삽입할 값이 모든 원소보다 작아서 맨 앞에 들어가야 하는 경우가 문제였다. 내부 루프가 끝까지 돌면 j는 0(첫 번째 원소의 인덱스)에서 끝날 것이고, 그렇다면 j+1은 1이 되어 두 번째 위치에 삽입되는 것 아닌가? 그래서 첫 번째 위치(인덱스 0)에 삽입하려면 if문으로 j가 0인 경우를 따로 처리하거나, 아예 삽입 위치를 기억할 별도의 변수를 선언해서 계산해야 하는 줄 알았다
실제로 어떻게 동작하는가
하지만 실제로는 그런 별도의 처리가 전혀 필요 없다. 이유는 for문의 동작 방식 때문이다.
내부 루프는 for (j = i - 1; j >= 0; j--)로 구성되어 있다. 이 루프가 끝까지 실행되면, 마지막 반복에서 j가 0일 때 비교와 이동 작업이 수행된 후에 j--가 자동으로 실행된다. 즉, j는 0에서 멈추는 것이 아니라 0에서 한 번 더 감소하여 -1이 된다.
여기서 핵심은 for문의 증감식(j–)은 루프 본문이 실행된 후, 조건 검사 전에 항상 실행된다는 점이다. 따라서 j가 0일 때 마지막 비교와 이동을 수행한 후 j–가 실행되어 j는 -1이 되고, 그 다음 j >= 0 조건을 확인할 때 거짓이 되어 루프를 빠져나오는 것이다.
그러므로 루프를 빠져나온 시점의 j 값은 0이 아니라 -1 이다. 그리고 arr[j + 1] = insertionData를 실행하면 arr[-1 + 1], 즉 arr[0]에 값이 삽입되어 자연스럽게 첫 번째 위치에 들어가게 됩니다
왜 이렇게 설계되었는가
이 설계의 우아함은 j의 의미가 일관성 있게 유지된다는 점이다. 루프가 끝난 후 j는 항상 “insertionData보다 작은 마지막 원소의 인덱스”를 가리킨다.
중간에 break로 빠져나온 경우, j는 실제로 작은 값의 인덱스를 가리키고 있습니다. 끝까지 돈 경우, 작은 값이 없다는 것은 “배열의 시작보다 앞”을 의미하므로 j는 -1이 됩니다. 따라서 두 경우 모두 j+1 위치에 삽입한다는 하나의 규칙만으로 모든 상황을 처리할 수 있다.
결국 별도의 조건문이나 추가 변수 없이, for문의 기본 동작 방식과 -1이라는 값을 활용하여 모든 경우를 우아하게 처리하는 것입니다. 이것이 삽입 정렬 구현의 핵심적인 통찰이다.
for (j = i - 1; j >= 0; j--) {
if (arr[j] > insertionData) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j + 1] = insertionData; // ← 여기가 핵심
중요한 포인트
- 내부 루프가 중간에 break로 종료되면 → j는 작은 원소의 인덱스
- 내부 루프가 끝까지 실행되면 → j는 -1
상황별 상세 분석
상황 1: 중간에 멈추는 경우 (일반적인 경우)
배열: [1, 3, 4, 5 | 2]
삽입할 원소: 2
═══════════════════════════════════════
j = 3 (원소 5)
├─ 5 > 2 → arr[4] = 5로 이동
├─ j-- 실행 → j = 2
└─ 계속 진행
j = 2 (원소 4)
├─ 4 > 2 → arr[3] = 4로 이동
├─ j-- 실행 → j = 1
└─ 계속 진행
j = 1 (원소 3)
├─ 3 > 2 → arr[2] = 3으로 이동
├─ j-- 실행 → j = 0
└─ 계속 진행
j = 0 (원소 1)
├─ 1 < 2 → break
└─ j는 0에서 멈춤 (j--가 실행되지 않음)
루프 종료 후
arr[j + 1] = arr[0 + 1] = arr[1]에 2 삽입
결과: [1, 2, 3, 4, 5]
↑
여기에 삽입
상황 2: 끝까지 도는 경우 (맨 앞에 삽입)
배열: [4 | 1]
삽입할 원소: 1
═══════════════════════════════════════
j = 0 (원소 4)
├─ 4 > 1 → arr[1] = 4로 이동
├─ j-- 실행 → j = -1 (핵심)
└─ j >= 0 조건 불만족 → 루프 종료
루프 종료 후:
arr[j + 1] = arr[-1 + 1] = arr[0]에 1 삽입
결과: [1, 4]
↑
여기에 삽입
코드 흐름 완벽 분석
/// 예제: [4 | 1] 정렬
int[] arr = {4, 1};
int i = 1; // 두 번째 원소부터 시작
int insertionData = arr[1]; // insertionData = 1
int j;
// === 내부 루프 시작 ===
for (j = i - 1; j >= 0; j--) { // j = 0부터 시작
// 1회차: j = 0
if (arr[0] > insertionData) { // 4 > 1? → true
arr[0 + 1] = arr[0]; // arr[1] = 4
// break 없음, 계속 진행
}
// j-- 자동 실행 → j = -1
// 조건 확인: -1 >= 0? → false
// 루프 종료!
}
// === 루프 종료 후 j의 값 ===
// j = -1 (마지막 j--의 결과)
// === 삽입 실행 ===
arr[j + 1] = insertionData;
// arr[-1 + 1] = 1
// arr[0] = 1
// 결과: [1, 4] ✓
결국 for문의 동작 원리를 완전히 이해하고 활용하는 능력이 아직 부족했던 것 같다. 알고리즘을 구현하다 보면, 반복문의 흐름 (특히 인덱스의 증감 시점과 종료 조건)을 정확히 이해하는 것이 핵심인데, 생각보다 이 부분이 많은 알고리즘의 기초를 이루고 있다는 걸 새삼 느꼈다
시간 복잡도 분석
비교 및 이동 횟수
최악의 경우 (역순 정렬된 배열)
[5, 4, 3, 2, 1] 1단계: 1번 비교 + 1번 이동 2단계: 2번 비교 + 2번 이동 3단계: 3번 비교 + 3번 이동 4단계: 4번 비교 + 4번 이동 총 연산: 1 + 2 + 3 + 4 = 10번 일반화: 1 + 2 + ... + (n-1) = n(n-1)/2
등차수열의 합
n(n-1) n² - n
───────── → ────────
2 2
빅오 표기법
- 최고차항: n²
- 시간 복잡도: O(n²)
간단하게 판별하는 방법은 중첩된 루프(최악의 경우) → O(n²)
경우별 시간 복잡도
| 경우 | 시간 복잡도 | 설명 |
| 최선 | O(n) | 이미 정렬된 배열 |
| 평균 | O(n²) | 무작위 배열 |
| 최악 | O(n²) | 역순 정렬된 배열 |
공간 복잡도
- O(1): 추가 메모리를 사용하지 않고 제자리에서 정렬(in-place sorting)
장점
- 구현이 간단: 직관적이고 이해하기 쉬움
- 안정 정렬: 동일한 값의 순서 유지
- 제자리 정렬: 추가 메모리 불필요
- 작은 데이터셋에 효율적: 오버헤드가 적음
단점
- 평균 / 최악 시간 복잡도 O(n²): 대용량 데이터에 비효율적
- 역순 배열에 매우 느림: 최악의 성능
삽입 정렬은 카드를 정렬하듯이 원소를 하나씩 적절한 위치에 삽입하는 직관적인 알고리즘이다. 평균적으로 O(n²)이지만, 거의 정렬된 데이터에서는 O(n)에 근접하여 매우 효율적이다. 이러한 특정 때문에 실제 프로덕션 정렬 알고리즘(Timsort 등)에서 작은 배열을 정렬할 때 사용된다