이진 삽입 정렬이란?
이진 삽입 정렬(Binary Insertion Sort)은 일반적인 삽입 정렬(Insertion Sort)을 개선한 특수한 형태의 정렬 알고리즘입니다. 배열에서 삽입할 요소가 들어갈 올바른 위치를 찾을 때 이진 탐색(Binary Search) 알고리즘을 활용하는 것이 핵심 특징입니다.
삽입 정렬은 각 요소를 배열 내 자신의 올바른 위치에 찾아 넣는 방식으로 동작하는 정렬 기법입니다. 반면 이진 탐색은 배열의 중간 지점부터 비교해 나가며 원하는 값을 찾는 탐색 기법입니다.
시간 복잡도 개선
이진 탐색의 시간 복잡도는 로그(logarithmic) 차수이기 때문에, 요소의 삽입 위치를 찾는 과정의 시간 복잡도 역시 O(log n) 수준으로 줄어듭니다. 다만 요소들을 실제로 한 칸씩 이동시키는 작업은 여전히 필요하므로 전체 정렬의 시간 복잡도는 최악의 경우 O(n²)입니다. 그럼에도 비교 연산 횟수가 크게 감소하기 때문에, 데이터가 거의 정렬된 상태이거나 비교 비용이 높은 환경에서 유용하게 사용됩니다.
동작 원리
- 배열의 두 번째 요소부터 시작하여 현재 요소(
selected)를 선택합니다. - 이미 정렬된 앞부분 배열에서 이진 탐색을 통해
selected가 들어갈 위치(loc)를 찾습니다. loc부터 현재 위치 직전까지의 요소를 한 칸씩 뒤로 밀고,selected를 해당 위치에 삽입합니다.
C++ 구현 예제
다음 프로그램은 기본적인 삽입 정렬 코드와 동일하지만, 표준 순차 탐색 방식 대신 이진 탐색을 사용해 삽입 위치를 결정합니다.
#include <iostream>
using namespace std;
int binarySearch(int arr[], int item, int low, int high) {
if (high <= low)
return (item > arr[low])? (low + 1): low;
int mid = (low + high)/2;
if(item == arr[mid])
return mid+1;
if(item > arr[mid])
return binarySearch(arr, item, mid+1, high);
return binarySearch(arr, item, low, mid-1);
}
void BinaryInsertionSort(int arr[], int n) {
int i, loc, j, k, selected;
for (i = 1; i < n; ++i) {
j = i - 1;
selected = arr[i];
loc = binarySearch(arr, selected, 0, j);
while (j >= loc) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = selected;
}
}
int main() {
int arr[] = {12, 56, 1, 67, 45, 8, 82, 16, 63, 23};
int n = sizeof(arr)/sizeof(arr[0]), i;
BinaryInsertionSort(arr, n);
cout<<"Sorted array is : \n";
for (i = 0; i < n; i++)
cout<<arr[i]<<"\t";
return 0;
}실행 결과
Sorted array is : 1 8 12 16 23 45 56 63 67 82
위 실행 결과에서 볼 수 있듯이, 무작위로 배치된 10개의 정수가 오름차순으로 성공적으로 정렬되었습니다. 이처럼 이진 삽입 정렬은 삽입 정렬의 단순한 구조를 유지하면서도 이진 탐색을 도입해 위치 탐색 효율을 높인 실용적인 알고리즘입니다.