이진 삽입 정렬 이진 검색 알고리즘을 사용하여 배열에서 삽입된 요소의 정확한 위치를 찾는 삽입 정렬의 특수 유형입니다.
삽입 정렬은 배열에서 요소의 올바른 위치를 찾은 다음 올바른 위치에 삽입하여 작동하는 정렬 기술입니다.
이진 검색 요소를 찾기 위해 배열의 중간을 찾아 작동하는 검색 기술입니다.
이진 탐색의 복잡도가 대수 차수이므로 탐색 알고리즘의 시간 복잡도도 대수 순으로 감소합니다.
이진 삽입 정렬의 구현. 이 프로그램은 간단한 삽입 정렬 프로그램이지만 표준 검색 기술 대신 이진 검색이 사용됩니다.
예시
#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