삽입 정렬
마지막 업데이트
삽입 정렬은 정렬된 배열을 한 번에 한 원소씩 만들어 갑니다. 다음 정렬되지 않은 원소("키")를 가져와, 정렬된 영역에서 그보다 큰 모든 원소를 한 칸씩 오른쪽으로 밀고, 키를 그 빈 자리에 넣습니다. 이는 대부분의 사람들이 손에 든 카드를 정렬하는 방식과 정확히 같습니다. 위의 재생 버튼을 눌러 각 키가 삽입되는 모습을 보거나, 밀어내는 과정을 하나씩 진행해 보세요.
삽입 정렬은 작거나 거의 정렬된 입력에서 매우 빠르며, 데이터가 이미 정렬되어 있으면 O(n)으로 동작합니다. 그래서 많은 하이브리드 정렬이 작은 부분 배열에 대해 삽입 정렬로 전환합니다.
시간 및 공간 복잡도
| 경우 | 복잡도 | 비고 |
|---|---|---|
| 최선의 경우 | O(n) | 이미 정렬됨 |
| 평균의 경우 | O(n²) | 무작위 순서 |
| 최악의 경우 | O(n²) | 역순 정렬 |
| 공간 | O(1) | 제자리 |
| 안정 | 예 | 같은 원소는 상대적 순서를 유지함 |
단계별 설명
| 단계 | 무슨 일이 일어나는가 |
|---|---|
| 1 | 첫 번째 원소를 크기가 1인 정렬된 영역으로 간주한다. |
| 2 | 다음 원소를 키로 가져온다. |
| 3 | 정렬된 영역에서 키보다 큰 모든 원소를 한 칸씩 오른쪽으로 민다. |
| 4 | 열린 빈자리에 키를 삽입한다. |
| 5 | 모든 원소가 삽입될 때까지 반복한다. |
풀이 예제
[5, 2, 4, 1] 정렬하기:
| 패스 | 배열 | 동작 |
|---|---|---|
| 시작 | [5, 2, 4, 1] | 5는 크기가 1인 초기 정렬 영역이다. |
| 1 | [2, 5, 4, 1] | 키 2: 5를 오른쪽으로 밀고 2를 맨 앞에 삽입. |
| 2 | [2, 4, 5, 1] | 키 4: 5를 오른쪽으로 밀고, 2는 더 작으므로 멈추고 4를 삽입. |
| 3 | [1, 2, 4, 5] | 키 1: 5, 4, 2를 오른쪽으로 밀고 1을 맨 앞에 삽입. |
| 완료 | [1, 2, 4, 5] | 모든 원소가 삽입되어 배열이 정렬됨. |
삽입 정렬을 사용해야 할 때
| 사용해야 할 때 | 피해야 할 때 |
|---|---|
배열이 작을 때(대략 n < 20). | 배열이 크고 무작위로 정렬되어 있을 때. |
데이터가 이미 거의 정렬되어 최선의 경우 O(n)을 얻을 때. | 보장된 최악의 경우 O(n log n)이 필요할 때. |
O(1) 추가 공간의 안정적인 제자리 정렬이 필요할 때. | 많은 이동을 수행하므로 원소 이동 비용이 클 때. |
| 데이터가 점진적으로 도착하며 온라인으로 정렬 상태를 유지해야 할 때. | 입력이 역순으로 정렬되어 최악의 경우 O(n²)가 될 때. |
Insertion Sort 코드
Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Insertion Sort 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.
Python로 구현한 Insertion Sort 코드
Python
1def insertion_sort(a):2 for i in range(1, len(a)):3 key = a[i]4 j = i - 15 # Shift larger elements one slot to the right6 while j >= 0 and a[j] > key:7 a[j + 1] = a[j]8 j -= 19 a[j + 1] = key10 return a11
12
13nums = [7, 3, 9, 1, 5, 8, 2]14print("Before:", nums)15insertion_sort(nums)16print("After: ", nums)JavaScript로 구현한 Insertion Sort 코드
JavaScript
1function insertionSort(a) {2 for (let i = 1; i < a.length; i++) {3 const key = a[i];4 let j = i - 1;5 // Shift larger elements right to open a slot for key6 while (j >= 0 && a[j] > key) {7 a[j + 1] = a[j];8 j--;9 }10 a[j + 1] = key;11 }12 return a;13}14
15const data = [5, 2, 9, 1, 7, 3];16console.log("Before:", data);17console.log("Sorted:", insertionSort([...data]));Java로 구현한 Insertion Sort 코드
Java
1import java.util.Arrays;2
3public class Main {4 static void insertionSort(int[] arr) {5 for (int i = 1; i < arr.length; i++) {6 int key = arr[i];7 int j = i - 1;8 // Shift larger elements one slot to the right9 while (j >= 0 && arr[j] > key) {10 arr[j + 1] = arr[j];11 j--;12 }13 arr[j + 1] = key;14 }15 }16
17 public static void main(String[] args) {18 int[] arr = {7, 3, 9, 1, 5, 8, 2};19 System.out.println("Before: " + Arrays.toString(arr));20 insertionSort(arr);21 System.out.println("After: " + Arrays.toString(arr));22 }23}C++로 구현한 Insertion Sort 코드
C++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5 for (int x : a) std::cout << x << " ";6 std::cout << "\n";7}8
9void insertionSort(std::vector<int>& a) {10 for (size_t i = 1; i < a.size(); ++i) {11 int key = a[i];12 int j = static_cast<int>(i) - 1;13 // Shift larger elements one slot to the right14 while (j >= 0 && a[j] > key) {15 a[j + 1] = a[j];16 --j;17 }18 a[j + 1] = key;19 }20}21
22int main() {23 std::vector<int> data = {7, 3, 9, 1, 5, 8, 2};24 std::cout << "Before: ";25 printVec(data);26 insertionSort(data);27 std::cout << "After: ";28 printVec(data);29 return 0;30}C로 구현한 Insertion Sort 코드
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void insertionSort(int a[], int n) {9 for (int i = 1; i < n; i++) {10 int key = a[i];11 int j = i - 1;12 // Shift larger elements one slot to the right13 while (j >= 0 && a[j] > key) {14 a[j + 1] = a[j];15 j--;16 }17 a[j + 1] = key;18 }19}20
21int main(void) {22 int data[] = {7, 3, 9, 1, 5, 8, 2};23 int n = sizeof(data) / sizeof(data[0]);24 printf("Before: ");25 printArr(data, n);26 insertionSort(data, n);27 printf("After: ");28 printArr(data, n);29 return 0;30}삽입 정렬 자주 묻는 질문
삽입 정렬의 시간 복잡도는 얼마인가요?
삽입 정렬은 평균과 최악의 경우
O(n²)이지만, 이미 정렬되었거나 거의 정렬된 배열에서는 O(n)입니다. 추가 공간은 O(1)을 사용합니다.삽입 정렬은 안정적인가요?
예. 삽입 정렬은 키보다 엄격히 큰 원소만 밀어내므로, 같은 원소가 서로를 앞지르는 일이 없고 상대적 순서가 보존됩니다.
삽입 정렬은 언제 사용해야 하나요?
작은 배열이나 이미 거의 정렬된 데이터에 사용하세요. 낮은 오버헤드와 적응적인 최선의 경우 덕분에 Timsort 같은 하이브리드 알고리즘은 작은 구간에 삽입 정렬을 사용합니다.
삽입 정렬과 버블 정렬의 차이는 무엇인가요?
둘 다
O(n²) 비교 정렬이지만, 삽입 정렬은 키를 위한 빈자리를 열기 위해 원소를 밀어내는 반면, 버블 정렬은 순서가 뒤바뀐 인접 쌍을 반복적으로 교환합니다. 삽입 정렬은 대개 쓰기 횟수가 적고, 특히 최선의 경우 O(n)에 도달하는 거의 정렬된 데이터에서 실제로 더 좋은 성능을 냅니다.왜 삽입 정렬이 작은 배열에서 병합 정렬보다 빠른가요?
삽입 정렬은 상수 배수 오버헤드가 매우 낮고 재귀나 추가 메모리 할당이 없어서, 점근적 복잡도가 더 나쁨에도 작은 입력에서는
O(n log n) 정렬을 앞섭니다. 바로 이 때문에 Timsort와 introsort 같은 하이브리드 정렬은 작은 부분 배열에 대해 삽입 정렬로 전환합니다.삽입 정렬은 연결 리스트와 배열 중 어느 쪽에서 더 잘 동작하나요?
삽입 정렬은 보통 원소 이동이 주요 비용인 배열용으로 작성됩니다. 연결 리스트에서는 노드를 제자리에 이어 붙여 이동을 피할 수 있지만 빠른 임의 접근을 잃게 되므로, 삽입 위치를 찾는 데 여전히 원소당 선형 시간이 걸리고 전체 비용은
O(n²)로 유지됩니다.관련 자료
더 많은 시각화
