이진 삽입 정렬(Binary Insertion Sort)은 전통적인 삽입 정렬에 이진 탐색(Binary Search)을 결합해 성능을 개선한 정렬 알고리즘입니다. 매 반복마다 현재 인덱스의 요소를 삽입할 올바른 위치를 이진 탐색으로 먼저 찾아내고, 그 위치의 기존 요소들을 한 칸씩 오른쪽으로 이동시킨 뒤 해당 요소를 제자리에 배치합니다.
일반적인 삽입 정렬은 삽입 위치를 찾기 위해 최악의 경우 앞쪽의 모든 요소와 하나씩 비교해야 합니다. 반면 이진 삽입 정렬은 이미 정렬된 구간에서 이진 탐색을 활용해 비교 횟수를 로그(log) 수준으로 크게 줄일 수 있습니다. 다만 요소를 실제로 이동시키는 비용은 그대로 남아 있으므로 전체 시간 복잡도는 여전히 O(n²)이며, 비교 연산 비용이 상대적으로 큰 환경에서 특히 유용합니다.
이진 삽입 정렬의 동작 단계
- 두 번째 요소부터 시작하여 현재 요소를 키(key)로 지정합니다.
- 왼쪽의 정렬된 구간을 대상으로 이진 탐색을 수행해 키가 들어갈 위치를 찾습니다.
- 찾은 위치부터 키의 원래 위치까지 요소들을 한 칸씩 오른쪽으로 밀어냅니다.
- 빈자리에 키를 삽입하고 다음 요소로 이동합니다.
- 모든 요소에 대해 위 과정을 반복하면 배열 전체가 정렬됩니다.
자바 예제 코드
다음은 자바로 작성한 이진 삽입 정렬의 전체 예제입니다.
public class Demo {
void binaryInsertionSort(int[] my_arr) {
for (int i = 1; i < my_arr.length; i++) {
int key = my_arr[i];
int left = 0;
int right = i;
while (left < right) {
int mid = (left + right) / 2;
if (my_arr[mid] <= key)
left = mid + 1;
else
right = mid;
}
for (int j = i; j > left; j--)
my_arr[j] = my_arr[j - 1];
my_arr[left] = key;
}
}
void printValues(int[] my_arr) {
for (int value : my_arr)
System.out.print(value + " ");
System.out.println();
}
public static void main(String[] args) {
Demo my_object = new Demo();
int[] my_arr = { 6, 8, 34, 21, 0, 1, 98, 64, 6 };
System.out.println("배열의 원소:");
my_object.printValues(my_arr);
my_object.binaryInsertionSort(my_arr);
System.out.println("이진 삽입 정렬 수행 후 배열:");
my_object.printValues(my_arr);
}
}실행 결과
배열의 원소:
6 8 34 21 0 1 98 64 6
이진 삽입 정렬 수행 후 배열:
0 1 6 6 8 21 34 64 98시간 복잡도 및 특징
- 최선의 경우: O(n log n) — 이미 정렬된 배열이라도 이진 탐색 비교는 수행되지만, 요소 이동은 발생하지 않습니다.
- 평균·최악의 경우: O(n²) — 삽입 위치를 빠르게 찾더라도 요소를 밀어내는 데 선형 시간이 소요됩니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 제자리(in-place) 정렬이 가능합니다.
- 안정성: 안정 정렬(stable sort)로, 값이 같은 요소들의 상대적인 순서가 유지됩니다.
이처럼 이진 삽입 정렬은 비교 횟수를 줄여 일반 삽입 정렬보다 효율적이며, 데이터 양이 적거나 거의 정렬된 데이터를 다룰 때 좋은 선택지가 됩니다.