삽입 정렬 (Insertion Sort)

삽입 정렬(Insertion Sort)은 두 번째 요소부터 시작하여 그 앞의 이미 정렬된 부분(Sorted Portion)과 비교해 자신이 들어갈 올바른 위치를 찾아 삽입(Insert)하는 알고리즘입니다. 손에 쥔 트럼프 카드들을 오름차순으로 정리할 때 사용하는 방법과 원리가 완전히 동일합니다.

1. 삽입 정렬의 작동 원리

선택 정렬이나 버블 정렬에 비해 실질적인 데이터 이동 횟수가 적어 기본 정렬 알고리즘 중에서는 가장 빠르다고 평가받습니다.
● 기준 설정(Key) : 두 번째 위치(인덱스 1)의 값을 Key로 지정하고 시작합니다.
● 밀어내기(Shifting) : 앞쪽의 정렬된 요소들을 역순으로 탐색하며 Key보다 큰 값이 있으면 그 값을 오른쪽으로 한 칸씩 밉니다.
● 삽입(Insertion) : Key보다 작거나 같은 값을 만나면 탐색을 멈추고, 그 바로 뒷자리에 Key를 꽂아 넣습니다.

2. 시간 및 공간 복잡도 분석

평가 기준	복잡도	심층 설명
최선 시간 복잡도 (Best)	O(N)	배열이 이미 정렬되어 있는 경우, 앞 요소와 단 한 번만 비교하고 바로 다음 요소로 넘어가기 때문에 탐색 속도가 압도적으로 빠릅니다.
최악/평균 시간 복잡도	O(N²)	배열이 역순으로 정렬되어 있다면 매번 첫 번째 자리까지 모든 요소를 밀어내야(Shift) 하므로 엄청난 오버헤드가 발생합니다.
공간 복잡도	O(1)	주어진 배열 안에서 값들을 Shift하고 끼워 넣는 제자리 정렬이므로 추가 공간이 불필요합니다.

💡 실무 지식: 안정 정렬(Stable Sort)과 Timsort

삽입 정렬은 중복된 값의 원래 순서를 그대로 유지해주는 안정 정렬(Stable Sort)입니다. O(N²) 이라서 실무에서 단독으로는 안 쓰이지만, 크기가 아주 작은 배열이거나 이미 거의 정렬된 배열에서는 퀵 정렬보다도 훨씬 빠르다는 엄청난 장점이 있습니다. 이 성질을 이용하여 V8 자바스크립트 엔진이나 Python은 '일정 크기 이하로 분할된 배열'을 정렬할 때 병합 정렬과 삽입 정렬을 섞어 쓰는 Timsort 하이브리드 알고리즘을 사용합니다.

// JavaScript 구현 function insertionSort(arr) { const n = arr.length; console.log("초기 배열:", arr); // 두 번째 요소(인덱스 1)부터 탐색 시작 for (let i = 1; i < n; i++) { let key = arr[i]; let j = i - 1; // key보다 큰 값들은 한 칸씩 오른쪽으로 이동(Shift) while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } // 알맞은 위치에 key 삽입 arr[j + 1] = key; } return arr; } const arr = [5, 3, 1, 4, 2]; console.log("정렬 결과:", insertionSort(arr));

평가 기준

복잡도

심층 설명

최선 시간 복잡도 (Best)

O(N)

배열이 이미 정렬되어 있는 경우, 앞 요소와 단 한 번만 비교하고 바로 다음 요소로 넘어가기 때문에 탐색 속도가 압도적으로 빠릅니다.

최악/평균 시간 복잡도

O(N²)

배열이 역순으로 정렬되어 있다면 매번 첫 번째 자리까지 모든 요소를 밀어내야(Shift) 하므로 엄청난 오버헤드가 발생합니다.

공간 복잡도

O(1)

주어진 배열 안에서 값들을 Shift하고 끼워 넣는 제자리 정렬이므로 추가 공간이 불필요합니다.